BOJ 6087 레이저 통신

www.acmicpc.net/problem/6087

6087번: 레이저 통신

 

BFS를 하면서 회전이 총 몇 번 일어났는지 체크해주면 되는데

처음엔 방향 dir 벡터를 선언하고 그 방향과 다르면 +1 해주는 식으로 접근했다가

더 좋은 풀이가 보여서 참고했다.

 

결국 일직선으로 얼마나 갈 수 있는지를 확인하는 게 중요한데

BFS로 범위를 체크하는 부분에서 while문을 사용해서 범위가 끝날 때까지 직진하도록 한다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
 
struct P { int x, y; };
int n, m;
int vis[101][101];
char a[101][101];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<P> node;
queue<P> q;
 
int bfs(int x, int y) {
    vis[x][y] = 0;
    q.push({ x,y });
 
    while (!q.empty()) {
        P cur = q.front(); q.pop();    
        if (cur.x == node[1].x && cur.y == node[1].y) return vis[cur.x][cur.y] - 1;
        for (int i = 0; i < 4; ++i) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            while (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (a[nx][ny] == '*') break;
                if (!vis[nx][ny]) {
                    vis[nx][ny] = vis[cur.x][cur.y] + 1;
                    q.push({ nx,ny });
                }
                nx += dx[i];
                ny += dy[i];
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> m >> n;
    for (int i=0;i<n;++i)
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            if (a[i][j] == 'C') node.push_back({ i,j });
        }
 
    cout << bfs(node[0].x, node[0].y) << endl;
 
    return 0;
}

 

그 외에는 딱히 어려울 것이 없었다.