[이것이 코딩 테스트다 with Python] 미로 탈출(Java)

Goal

“이것이 코딩 테스트다 with Python” 교재의 문제를 분석하고 코드와 함께 이해해보기 위한 글입니다.

문제 분석

주어지는 조건이 BFS로 최단 거리를 풀라는 의도가 담겨져 있다고 느껴지네요. 시작 포인트부터 상하좌우를 살펴 맵 밖으로 나가지 않도록 하는 조건과 이전 위치보다 탈출구에 가까운지를 확인하는 조건을 갖는 BFS를 구현해 최단 거리를 출력하는 프로그램을 작성해보겠습니다.

코드 구현

public class MazeEscape { //p152
    static int row, col;
    static int[][] maze;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        maze = new int[row][col];

        for (int i = 0; i < row; i++) {
            String[] splitStr = br.readLine().split("");
            for (int j = 0; j < col; j++) {
                maze[i][j] = Integer.parseInt(splitStr[j]);
            }
        }

        System.out.println(bfs(0, 0));
    }

    private static int bfs(int x, int y) {
        Queue<Integer> que = new LinkedList<>();
        que.add(x);
        que.add(y);
        int cnt = 1;
        int nx;
        int ny;

        while (!que.isEmpty()) {
            x = que.poll();
            y = que.poll();
            maze[x][y] = 0; //방문처리

            for (int i = 0; i < 4; i++) {
                nx = x + dx[i];
                ny = y + dy[i];
                if (nx < 0 || nx > row - 1 || ny < 0 || ny > col - 1) continue;
                if (maze[nx][ny] == 1 && (nx > x || ny > y)) {
                    cnt++;
                    que.add(nx);
                    que.add(ny);
                }
            }
        }
        return cnt;
    }
}