[BOJ] 3709. 레이저빔은 어디로

*(0,0)인 경우만 잘 파악하면 된다. 

-우향우 거울이 있는 곳으로 이전과 같은 방향으로 또 가게 되는 경우 (무한루프에 빠짐)

-갈 수 있는 경로를 다 가봤는데 맵을 떠나지 못하는 경우(queue를 다 돌았는데 보드 밖으로 못 나간 경우)

 

*visited는 방문 표시를 하는 배열로, 3차원으로 기록한다. (좌표, 방향) -> 우향우 거울이 있는 곳으로 이전과 같은 방향으로 다시 들어오면 (0,0)을 반환한다. 

 

 

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <vector> #include <cstring> #include <queue> using namespace std; int n; int map[52][52]; bool visited[52][52][4]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }; typedef pair<int, int> pp; typedef pair<int, pp> ipp; pp bfs(int sx, int sy, int d) { queue<ipp> q; q.push(ipp(d, pp(sx, sy))); while (!q.empty()) { int x = q.front().second.first; int y = q.front().second.second; int dir = q.front().first; q.pop(); int nx = x, ny = y; while (nx + dx[dir] >= 1 && nx + dx[dir] <= n && ny + dy[dir] >= 1 && ny + dy[dir] <= n && map[nx + dx[dir]][ny + dy[dir]] != 1 && !visited[nx + dx[dir]][ny + dy[dir]][dir]) { nx += dx[dir]; ny += dy[dir]; } if (visited[nx + dx[dir]][ny + dy[dir]][dir]) return pp({ 0,0 }); //똑같은 곳을 또 가게 된다. if (nx+dx[dir] == 0 || nx + dx[dir] == n+1 || ny + dy[dir] == 0 || ny + dy[dir] == n+1) { return pp(nx + dx[dir], ny + dy[dir]); } if (map[nx + dx[dir]][ny + dy[dir]] == 1) { int n_dir = dir < 2 ? 3 - dir : dir - 2; visited[nx + dx[dir]][ny + dy[dir]][dir] = true; q.push(ipp(n_dir, pp(nx + dx[dir], ny + dy[dir]))); } } return pp({ 0,0 }); } int main() { int t; scanf("%d", &t); while (t--) { memset(map, 0, sizeof(map)); memset(visited, 0, sizeof(visited)); int r; scanf("%d %d", &n, &r); int x, y; for (int i = 0; i < r; i++) { scanf("%d %d", &x, &y); //거울이 있는 자리; map[x][y] = 1; } scanf("%d %d", &x, &y); //레이저빔자리 int dir = 0; if (x == 0) { //아래 방향으로 나아간다. dir = 1; } else if (y == 0) { //오른쪽 방향으로 나아간다. dir = 3; } else if (x == n + 1) { //위쪽 방향으로 나아간다. dir = 0; } else if (y == n + 1) { dir = 2; } pp dest = bfs(x, y, dir); printf("%d %d\n", dest.first, dest.second); } return 0; }