문제

이해

격자 정보는 다음과 같습니다.

'#' : 문 (목적지)
'.' : 빈 공간
'!' : 거울이 설치될 수 있는 공간
'*' : 벽

거울을 설치할 때는 항상 45도 대각선 방향으로 설치할 수 있습니다. 이 말은 빛의 진행방향을 바꾼다는 의미이기도 합니다.

우리는 거울을 설치하여 문에서 문까지 볼 수 있도록 해야 합니다. 즉, 빛이 어느 한 문에서 나온다고 가정하면 이 빛이 거울에 의해 다른 문까지 도달할 수 있어야 합니다.

문과 문이 보이는 경우 그 때의 설치된 거울의 갯수를 세고 가장 최소일 때의 값을 출력하면 됩니다.

접근

완전탐색이라고 생각해봅시다. 거울은 '!' 지역에 설치할 수도 설치하지 않을 수도 있습니다. 모든 경우의 수를 탐색하려면 부분집합 즉, '!' 의 갯수만큼 2를 곱해야 합니다. N이 최대 50이니 대략 2^2500이 나옵니다. 당연하게도 완전탐색은 하지 못합니다.

우리가 구해야 하는 답을 생각해봅시다. 거울의 최소갯수입니다. 거울을 최소한으로 배치하여 우리는 또 다른 문으로 가야합니다. 다시 말해, 거울의 갯수가 가중치가 될 수 있지 않을까라는 생각을 합니다.

한 점에서 BFS를 수행한다고 가정합니다. 만일 탐색 중 '!'을 만난다면 다음과 같은 분기로 나뉩니다.

1. 설치하지 않는다.
2. 진행방향의 왼쪽으로 반사한다.
3. 진행방향의 오른쪽으로 반사한다.

1번의 경우 설치하지 않기 때문에 가중치가 0 입니다. 2번과 3번의 경우 거울을 설치하기 때문에 가중치가 1 올라갑니다. 우리가 BFS를 수행할 때 가중치가 더 작은 0을 먼저 큐에 넣어 탐색하게 한다면?

다른 문에 빛이 도달하는 경우에 자연스럽게 거울을 최소 갯수로 쓰게 됩니다.

사실 이 개념은 0-1BFS입니다. 이전에 풀었던 "탈옥" 문제에서 활용되었던 알고리즘입니다. BFS에서는 보통 가중치가 1로 모두 같기 때문에 데이크스트라처럼 PQ를 사용하지 않습니다.

하지만 본 문제같이 가중치가 0 or 1인 경우에는 더 작은 0일 때를 먼저 방문해야 하기 때문에 큐에서 최소 가중치인 것만 뽑을 필요가 있습니다.

데이크스트라와 로직이 같기 때문에 pq를 써도 되지만 0-1BFS인 경우 가중치가 2가지 경우밖에 없기 때문에 덱을 이용해서 처음과 끝에 삽입하도록 하여도 됩니다.

풀이

private static int bfs() {
        boolean[][][] visited = new boolean[4][N][N];
        Deque<xy> dq = new ArrayDeque<>();
        for (int i = 0; i < 4; i++) {
            dq.add(new xy(start.x, start.y, i, 0));
            visited[i][start.x][start.y] = true;
        }

        while (!dq.isEmpty()) {
            xy cur = dq.poll();

            int nx = cur.x + d[0][cur.prevDirection];
            int ny = cur.y + d[1][cur.prevDirection];

            if (IsOutBound(nx, ny) || visited[cur.prevDirection][nx][ny] || board[nx][ny] == '*') {
                continue;
            }

            if (board[nx][ny] == '.') {
                visited[cur.prevDirection][nx][ny] = true;
                dq.addFirst(new xy(nx, ny, cur.prevDirection, cur.depth));
            } else if (board[nx][ny] == '!') {
                int d1 = (cur.prevDirection + 1) % 4;
                int d2 = (cur.prevDirection + 3) % 4;
                int d3 = cur.prevDirection;

                visited[d1][nx][ny] = true;
                dq.addLast(new xy(nx, ny, d1, cur.depth + 1));
                visited[d2][nx][ny] = true;
                dq.addLast(new xy(nx, ny, d2, cur.depth + 1));
                visited[d3][nx][ny] = true;
                dq.addFirst(new xy(nx, ny, d3, cur.depth));
            } else {
                return cur.depth;
            }
        }

        return -1;
    }

위 코드는 BFS를 수행하는 과정입니다. 덱을 이용해서 가중치가 1인 경우 뒤, 0인 경우 앞에 삽입합니다.

'!'을 만날 경우 3가지 경우로 분기된다는 것만 유의하시면 되겠습니다.

전체 코드

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

public class Main {
    static final int[][] d = { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } };

    static class xy {
        int x;
        int y;
        int prevDirection;
        int depth;

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

    }

    static int N;
    static char[][] board;
    static xy start;

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

        N = Integer.parseInt(br.readLine());
        board = new char[N][N];
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < N; j++) {
                board[i][j] = s.charAt(j);
                if (board[i][j] == '#' && start == null) {
                    start = new xy(i, j, 0, 0);
                    board[i][j] = '.';
                }
            }
        }

        System.out.println(bfs());

    }

    private static int bfs() {
        boolean[][][] visited = new boolean[4][N][N];
        Deque<xy> dq = new ArrayDeque<>();
        for (int i = 0; i < 4; i++) {
            dq.add(new xy(start.x, start.y, i, 0));
            visited[i][start.x][start.y] = true;
        }

        while (!dq.isEmpty()) {
            xy cur = dq.poll();

            int nx = cur.x + d[0][cur.prevDirection];
            int ny = cur.y + d[1][cur.prevDirection];

            if (IsOutBound(nx, ny) || visited[cur.prevDirection][nx][ny] || board[nx][ny] == '*') {
                continue;
            }

            if (board[nx][ny] == '.') {
                visited[cur.prevDirection][nx][ny] = true;
                dq.addFirst(new xy(nx, ny, cur.prevDirection, cur.depth));
            } else if (board[nx][ny] == '!') {
                int d1 = (cur.prevDirection + 1) % 4;
                int d2 = (cur.prevDirection + 3) % 4;
                int d3 = cur.prevDirection;

                visited[d1][nx][ny] = true;
                dq.addLast(new xy(nx, ny, d1, cur.depth + 1));
                visited[d2][nx][ny] = true;
                dq.addLast(new xy(nx, ny, d2, cur.depth + 1));
                visited[d3][nx][ny] = true;
                dq.addFirst(new xy(nx, ny, d3, cur.depth));
            } else {
                return cur.depth;
            }
        }

        return -1;
    }

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

결과

리뷰

가중치가 서로 다른 BFS인 경우에 대해서 이해하고 있다면 쉽게 풀 수 있는 문제였던 것 같습니다.