** BFS

문제

이해

8x8 체스판이 주어집니다. 체스판의 가장 왼쪽 아랫 칸에 캐릭터가 위치하고 캐릭터는 가장 오른쪽 윗칸으로 이동해야 합니다.

체스판에는 벽이 있는데 이 벽은 1초마다 한 칸씩 아랫 행으로 내려갑니다. 캐릭터는 벽에 있는 곳에 갈 수도 없지만 캐릭터가 있는 곳에 벽이 움직여 도달하면 그 위치의 캐릭터는 이동할 수 없게 됩니다.

주어진 입력을 보고 캐릭터가 목적지에 도달할 수 있는지 출력해야 합니다.

접근

갈 수 있냐 없냐의 문제는 기본적인 탐색의 문제입니다. DFS, BFS 모두 가능하지만 DFS는 스택 메모리를 많이 사용하기 때문에 선택하지 않았습니다.

BFS로 탐색할 때 가장 중요한 것은 방문처리를 알맞게 하여 중복을 없애고 시간복잡도를 줄여야 합니다. 본 문제에서는 시간마다 맵이 바뀌는 변수가 존재합니다. 같은 위치라도 만일 초가 다르다면 다른 경우로 생각하여야 합니다.

따라서, 방문처리의 기준을 초와 위치로 한다면 BFS의 모든 경우의 수를 탐색할 수 있습니다. 구체적인 방법으로는 3차원 방문처리 배열을 생성하여 visited[시간][x][y] 로 구성하면 되겠습니다.

풀이

private static boolean bfs() {
        Queue<xy> q = new ArrayDeque<>();
        boolean[][][] visited = new boolean[1001][8][8];
        q.add(new xy(7, 0));
        visited[0][7][0] = true;
        int depth = 0;

        while (q.size() > 0) {
            // PrintForDebug();

            depth++;
            int qsize = q.size();

            while (qsize-- > 0) {
                xy cur = q.poll();

                if (board[cur.x][cur.y] == WALL) {
                    continue;
                }

                for (int i = 0; i < 9; i++) {
                    int nx = cur.x + d[0][i];
                    int ny = cur.y + d[1][i];

                    if (IsOutBound(nx, ny) || visited[depth][nx][ny] || board[nx][ny] == WALL) {
                        continue;
                    }

                    if (nx == 0 && ny == 7) {
                        return true;
                    }

                    q.add(new xy(nx, ny));
                    visited[depth][nx][ny] = true;
                }
            }

            boardUpdate();
        }

        return false;
    }

초 단위로 끊어서 BFS를 수행하고 9방향의 분기를 탐색합니다. (캐릭터는 가만히 있을 수도 있습니다.) 탐색 도중 (0, 7)인 목적지에 도달하면 true를 반환합니다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {

    static final int[][] d = { { 0, -1, -1, -1, 0, 1, 1, 1, 0 }, { 0, -1, 0, 1, 1, 1, 0, -1, -1 } };
    static final int WALL = 1;
    static final int GND = 0;

    static class xy {
        int x;
        int y;

        public xy(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

    static int[][] board = new int[8][8];

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

        for (int i = 0; i < 8; i++) {
            String s = br.readLine();
            for (int j = 0; j < 8; j++) {
                char c = s.charAt(j);
                switch (c) {
                    case '.':
                        board[i][j] = GND;
                        break;
                    case '#':
                        board[i][j] = WALL;
                        break;
                    default:
                        break;
                }
            }
        }

        System.out.println(bfs() ? 1 : 0);
    }

    private static boolean bfs() {
        Queue<xy> q = new ArrayDeque<>();
        boolean[][][] visited = new boolean[1001][8][8];
        q.add(new xy(7, 0));
        visited[0][7][0] = true;
        int depth = 0;

        while (q.size() > 0) {
            // PrintForDebug();

            depth++;
            int qsize = q.size();

            while (qsize-- > 0) {
                xy cur = q.poll();

                if (board[cur.x][cur.y] == WALL) {
                    continue;
                }

                for (int i = 0; i < 9; i++) {
                    int nx = cur.x + d[0][i];
                    int ny = cur.y + d[1][i];

                    if (IsOutBound(nx, ny) || visited[depth][nx][ny] || board[nx][ny] == WALL) {
                        continue;
                    }

                    if (nx == 0 && ny == 7) {
                        return true;
                    }

                    q.add(new xy(nx, ny));
                    visited[depth][nx][ny] = true;
                }
            }

            boardUpdate();
        }

        return false;
    }

    private static void PrintForDebug() {
        System.out.println("================");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == WALL) {
                    System.out.print('#');
                } else {
                    System.out.print('.');
                }
            }
            System.out.println();
        }
    }

    private static void boardUpdate() {
        int[][] newBoard = new int[8][8];

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == WALL && i < 7) {
                    newBoard[i + 1][j] = WALL;
                }
            }
        }

        board = newBoard;
    }

    private static boolean IsOutBound(int nx, int ny) {
        return nx < 0 || ny < 0 || nx >= 8 || ny >= 8;
    }

}

결과

리뷰

방문처리를 변형해야 하는 BFS 문제입니다.