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

문제

레이저박스라는 게임은 정사각형 모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 설치되어 있다. 레이저는 판의 끝에만 설치 될 수 있는데, 행의 맨 아래/맨 위, 열의 오른쪽 끝/왼쪽 끝에 설치 될 수 있다. 레이저에서 나온 빔은 그 행 혹은 열을 질러서 반대쪽을 비춘다.

게임은 우향우 거울을 임의의 칸마다 설치한 후, 레이저를 배치를 해 놓은 이후에 시작한다. 레이저를 켰을 때 나온 빔이 우향우 거울을 통과하면 진입한 방향과는 관계 없이 오른쪽으로 90도를 꺾어 다시 나아간다.

레이저 빔이 마지막으로 어느 좌표를 향해 비춰지는지 구하라.

입력

첫 줄에는 테스트케이스의 총 개수가 주어진다.

테스트케이스의 첫 줄에는 보드의 크기 n(1 ≤ n ≤ 50)과 우향우 거울의 개수 r(1 ≤ r ≤ 50)이 주어진다.

이어지는 r개의 줄에는 우향우 거울이 배치된 좌표 x y가 주어진다.(좌표는 1부터 시작한다) 중복된 좌표는 있을 수 없고, 매 칸마다 최대 1개의 우향우 거울이 놓일 수 있다.

마지막 줄에는 레이저의 좌표가 주어진다. 레이저는 행과 열의 끝, 즉 판 밖에 위치해야 하므로 레이저의 좌표에는 0 혹은 n + 1이 포함된다.

예를 들어, 2x2보드의 1행 맨 밑에서 위로 쏘아지는 레이저의 좌표는 (3, 1)로써 주어진다. 마찬가지로 6x6보드의 6열 왼쪽 끝에서 오른쪽 끝으로 쏘아지는 레이저의 좌표는 (6, 0)이 되겠다.

출력

매 테스트케이스마다 빔이 보드를 떠나는 좌표 X Y를 출력하라. 레이저의 좌표와 마찬가지로 빔은 보드 밖으로 떠나기에 좌표에는 0 혹은 n + 1이 포함된다.

만약 빔이 보드 밖을 떠나지 않을 경우의 출력은 0 0이 된다.

예제 입력 1

2
2 3
1 1
1 2
2 2
3 1
3 6
1 1
1 3
2 2
2 3
3 1
3 2
2 0

예제 출력 1

2 0
0 2

풀이

이 문제는 DFS(깊이 우선 탐색) 알고리즘을 이용해서 풀 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int[][] map;
    static boolean[][][] visited;
    static int N;
    static boolean flag;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

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

        for(int i=0; i<T; i++) {
            String[] input = br.readLine().split(" ");

            N = Integer.parseInt(input[0]);
            int M = Integer.parseInt(input[1]);
            map = new int[N+2][N+2];
            visited = new boolean[N+2][N+2][4];
            flag = false;

            for(int j=0 ;j<M; j++) {
                input = br.readLine().split(" ");
                map[Integer.parseInt(input[0])][Integer.parseInt(input[1])] = 1;
            }

            input = br.readLine().split(" ");
            int startX = Integer.parseInt(input[0]);
            int startY = Integer.parseInt(input[1]);

            if(startX==0)
                dfs(startX+1, startY, 2);

            else if(startY==0)
                dfs(startX, startY+1, 1);

            else if(startX==N+1)
                dfs(startX-1, startY, 0);

            else
                dfs(startX, startY-1, 3);

            if(!flag)
                System.out.println("0 0");
        }
    }

    public static void dfs(int x, int y, int d) {
        if(x==0 || x==N+1 || y==0 || y==N+1) {
            flag = true;
            System.out.println(x+" "+y);
            return ;
        }

        int nd = d;

        if(map[x][y]==1) {
            nd = d+1;
            if(nd==4) nd=0;
        }

        int nx = x+dx[nd];
        int ny = y+dy[nd];

        if(!visited[nx][ny][nd]) {
            visited[nx][ny][nd] = true;
            dfs(nx, ny, nd);
        }
    }
}