[BOJ] 6087: 레이저 통신

문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

 

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

 

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

 

풀이

같은 노드에 대하여 몇 개의 거울을 사용하여 도달할 수 있는지는 단순히 BFS로 탐색할 수 없다.

이미 방문했던 노드를 더 좋은 방법으로 접근하는 방법을 찾아도 다시 방문할 수 없기 때문이다.

따라서 다익스트라의 개념을 사용하여 노드의 값을 저장해야 하기 때문에 이렇게 코드를 작성하였다.

if(cur.direction == dir || cur.direction == Node.DIR.NO){
    if(visited[ny][nx] > cur.mirror) {
        q.offer(new Node(ny, nx, dir, cur.mirror));
        visited[ny][nx] = cur.mirror;
    }
} else {
    if(visited[ny][nx] > cur.mirror + 1) {
        q.offer(new Node(ny, nx, dir, cur.mirror + 1));
        visited[ny][nx] = cur.mirror + 1;
    }
}

하지만 visited와 cur.mirror를 비교하는 분기문에서 지금까지 사용한 거울의 개수가 같더라도

다른 방향으로 접근하였다면 다른 노드 접근으로 보아야 하기때문에 아래와 같이 수정하였다.

if(cur.direction == dir || cur.direction == Node.DIR.NO){
    if(visited[ny][nx] >= cur.mirror) {
        q.offer(new Node(ny, nx, dir, cur.mirror));
        visited[ny][nx] = cur.mirror;
    }
} else {
    if(visited[ny][nx] >= cur.mirror + 1) {
        q.offer(new Node(ny, nx, dir, cur.mirror + 1));
        visited[ny][nx] = cur.mirror + 1;
    }
}

코드

---

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

public class Main {
    static int[] dy = {-1, 1, 0, 0, 0};
    static int[] dx = {0, 0, -1, 1, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());
        char[][] map = new char[H][W];
        Node[] connections = new Node[2];
        int cursor = 0;


        for (int i = 0; i < H; i++) {
            char[] line = br.readLine().toCharArray();
            map[i] = line;
            for (int j = 0; j < W; j++) {
                if(map[i][j] == 'C'){
                    connections[cursor++] = new Node(i, j, Node.DIR.NO, 0);
                }
            }
        }

        int[][] visited = new int[H][W];
        for (int i = 0; i < H; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        visited[connections[0].y][connections[0].x] = 0;
        int res = Integer.MAX_VALUE;
        Queue<Node> q = new ArrayDeque<>();
        q.offer(connections[0]);

        while (!q.isEmpty()){
            Node cur = q.poll();

            if(cur.equals(connections[1])){
                res = Math.min(res, cur.mirror);
            }

            for (Node.DIR dir : Node.DIR.values()) {
                int ny = cur.y + dy[dir.ordinal()];
                int nx = cur.x + dx[dir.ordinal()];

                if(0 > ny || ny >= H || 0 > nx || nx >= W || dir == Node.DIR.NO)
                    continue;

                if(map[ny][nx] == '*')
                    continue;

                if(cur.direction == dir || cur.direction == Node.DIR.NO){
                    if(visited[ny][nx] >= cur.mirror) {
                        q.offer(new Node(ny, nx, dir, cur.mirror));
                        visited[ny][nx] = cur.mirror;
                    }
                } else {
                    if(visited[ny][nx] >= cur.mirror + 1) {
                        q.offer(new Node(ny, nx, dir, cur.mirror + 1));
                        visited[ny][nx] = cur.mirror + 1;
                    }
                }
            }
        }
        System.out.println(res);
    }

    static class Node{
        enum DIR {UP, DOWM, LEFT, RIGHT, NO};
        int y;
        int x;
        DIR direction;
        int mirror;

        @Override
        public boolean equals(Object obj) {
            Node other = (Node) obj;
            return this.y == other.y && this.x == other.x;
        }

        public Node(int y, int x, DIR dir, int mirror) {
            this.y = y;
            this.x = x;
            this.direction = dir;
            this.mirror = mirror;
        }
    }
}