[백준] 3709번 : 레이저빔은 어디로

3709번: 레이저빔은 어디로

---

[DFS]

N x N 격자의 밖에서 레이저빔을 쐈을 때 우향우 거울을 통해 반사되어 최종적으로 레이저빔이 도착한 위치를 찾는 문제.

레이저 빔은 이미 지나온 곳도 다시 지날 수 있다. 그렇다고 해서 방문을 했는지 여부를 체크하지 않으면 안된다. 문제에서 주어진 것을 보면 알 수 있듯, 레이저빔이 격자 밖을 빠져나가지 못하면 0 0을 출력하라고 한 것을 보아 방문을 체크하지 않는다면 무한루프에 빠져 Stackoverflow 에러가 발생할 것이다. 그러면 어떻게 방문 체크를 하는가? 이미 지나온 정점을 다시 방문할 수 있어야 하고, 방문을 체크하는 방법.

 

그 방법은 여러 개가 존재하겠으나, 나는 방향(상하좌우)을 추가하여 한 정점에 최대 4번 방문할 수 있게 하였다.  그리고 우향우 거울은 들어온 방향에 관계없이 무조건 오른쪽으로 레이저빔을 틀어주므로 상 -> 우 -> 하 -> 좌 -> 상 -> ...이런 식으로 계속 갈 것이다. 따라서 방향에 인덱스를 부여하고 % 4 연산을 통해 오른쪽으로 틀어주는 것을 구현하도록 한다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int n, endY, endX;
    static int[] Y = {-1, 0, 1, 0}, X = {0, 1, 0, -1}; //상 -> 우 -> 하 -> 좌
    static boolean[][][] visit;
    static int[][] map;

    static void init(){
        for(int i=0; i<=n+1; i++){
            map[0][i] = -1; map[n+1][i] = -1;
            map[i][0] = -1; map[i][n+1] = -1;
        }
    }

    static void DFS(int y, int x, int dir) {
        if(map[y][x] < 0){
            endY = y;
            endX = x;
            return;
        }
        if(visit[y][x][dir]) {
            endY = 0;
            endX = 0;
            return;
        }

        visit[y][x][dir] = true;
        
        if(map[y][x] == 1) //우향우 거울(1)이면 우로 회전
            dir = (dir + 1) % 4;

        int ny = y + Y[dir];
        int nx = x + X[dir];

        DFS(ny, nx, dir);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for(int a=0; a<t; a++){

            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            endX = -1;
            endY = -1;
            int dir = -1; //방향(상,하,좌,우)
            map = new int[52][52];
            visit = new boolean[52][52][4];
            init();

            /* 우향우 거울 좌표 */
            for(int i=0; i<r; i++){
                st = new StringTokenizer(br.readLine());

                int y = Integer.parseInt(st.nextToken());
                int x = Integer.parseInt(st.nextToken());

                map[y][x] = 1;
            }
            /* 레이저 빔 좌표 */
            st = new StringTokenizer(br.readLine());

            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            if(x == n+1)     dir = 3; //좌
            else if(y == n+1)dir = 0; //상
            else if(x == 0)  dir = 1; //우
            else             dir = 2; //하

            DFS(y+Y[dir], x+X[dir], dir);

            System.out.println(endY + " " + endX);
        }
    }
}