[백준] 6087번 : 레이저 통신 - JAVA [자바]

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

---

bfs 알고리즘 문제이다.

1. 출발점 C 에서 도착점 C 까지의 경로 중 최소 갯수의 거울을 사용한 경우를 구한다.

2. 방문 여부 배열에 거울의 갯수를 넣어서 더 적은 갯수로 도달한 경우, 큐에 추가하여 탐색한다.

3. 우선 순위 큐를 사용하여 더 적은 갯수의 거울을 사용한 경우를 먼저 탐색한다.

4. 현재 타일에서 다음 타일로 넘어갈 때, 그 전의 타일에서 현재 타일로 온 레이저의 방향에 따라 거울의 갯수가 달라진다.

   4.1 만약 그 전 타일에서 현재 타일로 위 방향의 레이저로 왔을 경우, 현재 타일에서 다음 타일로 가는 방향이 왼쪽 혹은 오른쪽일 경우 거울의 갯수 + 1이 되며

   4.2 현재 타일에서 다음 타일로 가는 방향이 같은 방향 즉, 윗 방향이라면 거울의 갯수는 똑같다.

   4.3 또한 180도 방향이라면 불가능한 경우이므로 탐색하지 않는다.

5. 즉, 방문 배열을 어떠한 방향으로 왔는지에 대한 것도 추가하여 visited = new int[H][W][4] 로 정의하여 (0-상, 1-좌, 2-하, 3-우) 방향에 따른 거울의 갯수를 비교할 수 있게 한다.

---

그 전 타일에서 현재 타일로 온 레이저의 방향에 대해 (0-상, 1-좌, 2-하, 3-우) 라고 생각하며 현재 타일에서 다음 타일로 넘어갈 때

static int[] xMove = {-1, 0, 1, 0};
static int[] yMove = {0, -1, 0, 1};

위의 배열을 사용하며 움직이는 방향도 상, 좌, 하, 우 순서라는 것을 기억하고 풀어야 한다.

point current = queue.poll();

for (int i = 0; i < 4; i++) {
	int newX = current.x + xMove[i];
    int newY = current.y + yMove[i];


	if (newX < 0 || newY < 0 || newX >= H || newY >= W) continue;

	if (map[newX][newY] == '*') continue;


	// 180 회전이라면 갈 수 없는 구조이므로 패스
    if (Math.abs(i - current.dir) == 2) continue;

	// 90 회전을 해야 한다면 거울의 갯수 +1
    int nextMirror = (current.dir == i) ? current.mirrors : current.mirrors + 1;

위의 현재 타일에서 다음 타일로 넘어갈 때, xMove 와 yMove 배열을 통해 움직이는 것을 보자.

만약 현재 레이저의 방향 (current.dir)이 0(상)일 경우, i는 1(좌)인 경우를 보자.
90도 회전이므로 즉, 0 != 1 이므로 거울의 갯수는 + 1이 된다.

다음으로 현재 레이저의 방향 (current.dir)이 0(상)일 경우, i는 2(하)인 경우를 보자.

i - current.dir 이 2이므로 이는 180도 회전이라고 생각하며 이는 불가능한 경우이므로 continue를 한다.

---

public class bj6087 {
    static char[][] map;
    static int[][][] visited;
    static int[] xMove = {-1, 0, 1, 0};
    static int[] yMove = {0, -1, 0, 1};
    static point[] cPoint;
    static int W, H, ANSWER = 100000;
    static PriorityQueue<point> queue = new PriorityQueue<>();

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

        String[] split = br.readLine().split(" ");
        W = Integer.parseInt(split[0]);
        H = Integer.parseInt(split[1]);

        map = new char[H][W];
        visited = new int[H][W][4];
        cPoint = new point[2];

        for (int i = 0, idx = 0; i < H; i++) {
            String line = br.readLine();
            map[i] = line.toCharArray();
            for (int j = 0; j < W; j++) {
            	// bfs 알고리즘 도중
                // 0, 1, 2, 3 범위에 들어가지 않도록 방향을 -5로 지정
                if (map[i][j] == 'C') cPoint[idx++] = new point(i, j, -5, -1);
            }
        }

        bfs(cPoint[0]);

        System.out.println(ANSWER);
        br.close();
    }

    public static void bfs(point start) {
        point c = cPoint[1];
        queue.add(start);

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                Arrays.fill(visited[i][j], Integer.MAX_VALUE);
            }
        }

        while (!queue.isEmpty()) {
            point current = queue.poll();

            if (current.x == c.x && current.y == c.y) {
                ANSWER = Math.min(ANSWER, current.mirrors);
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int newX = current.x + xMove[i];
                int newY = current.y + yMove[i];


                if (newX < 0 || newY < 0 || newX >= H || newY >= W) continue;

                if (map[newX][newY] == '*') continue;


                // 180 회전이라면 갈 수 없는 구조이므로 패스
                if (Math.abs(i - current.dir) == 2) continue;

                // 90 회전을 해야 한다면 거울의 갯수 +1
                int nextMirror = (current.dir == i) ? current.mirrors : current.mirrors + 1;

                // 현재 방향에서 다음 newX, newY 위치로 갈때 사용한 미러의 갯수가
                // 더 적은 거울로 도달할 수 있는 경우가 생긴다면
                if (visited[newX][newY][i] > nextMirror) {
                    visited[newX][newY][i] = nextMirror;
                    queue.add(new point(newX, newY, i, nextMirror));
                }
            }
        }
    }

    public static class point implements Comparable<point> {
        int x, y, dir, mirrors;

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

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