백준 6087 자바 - 레이저 통신

https://www.acmicpc.net/problem/6087

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

코드

import java.io.*;
import java.util.*;

public class Main {
    private static int w, h;
    private static char[][] map;
    private static Node[] target = new Node[2];
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        map = new char[h][w];


        for (int i = 0, idx = 0; i < h; i++) {
            String s = br.readLine();
            map[i] = s.toCharArray();
            for (int j = 0; j < w; j++) {
                if (map[i][j] == 'C') target[idx++] = new Node(i, j, -5, -1);
            }
        }

        bw.write(String.valueOf(bfs(target[0])));
        bw.flush();
    }

    private static int bfs(Node start) {
        int min = Integer.MAX_VALUE;
        Node goal = target[1];
        PriorityQueue<Node> q = new PriorityQueue<>();
        int[][][] visited = new int[4][h][w];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < h; j++) {
                Arrays.fill(visited[i][j], Integer.MAX_VALUE);
            }
        }

        q.offer(start);

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

            if (now.x == goal.x && now.y == goal.y) {
                min = Math.min(min, now.mirrors);
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nextX = now.x + dx[i];
                int nextY = now.y + dy[i];
                int nextMirrors = (now.dir == i) ? now.mirrors : now.mirrors + 1;
                if (!isInRange(nextX, nextY) || map[nextX][nextY] == '*' || Math.abs(now.dir - i) == 2) continue;

                if (visited[i][nextX][nextY] > nextMirrors) {
                    q.offer(new Node(nextX, nextY, i, nextMirrors));
                    visited[i][nextX][nextY] = nextMirrors;
                }
            }
        }

        return min;
    }

    private static boolean isInRange(int x, int y) {
        return x >= 0 && x < h && y >= 0 && y < w;
    }

    private static class Node implements Comparable<Node> {
        int x, y, dir, mirrors;

        public Node(int x, int y, int dir, int mirrors) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.mirrors = mirrors;
        }

        @Override
        public int compareTo(Node o) {
            return this.mirrors - o.mirrors;
        }
    }
}

풀이

 visited를 3차원 배열로 두어 x좌표, y좌표 그리고 레이저의 방향을 저장한다. 이전의 레이저 방향이 왼쪽을 바라볼 때는 거울이 필요 없고, 위 아래는 1개가 필요, 오른쪽은 이동 불가다. 또한 주의할 점이 이미 방문한 지점이라도 거울 사용 횟수가 보다 적다면 배열 값을 갱신하고 다시 큐에 넣는다는 것이다.