[백준 Baekjoon] 6087번 레이저 통신 - JAVA

백준 Baekjoon 6087번 레이저 통신 - JAVA

---

문제 풀이

두 레이저를 최소한의 거울을 사용하여 연결하는 문제이다. 최소 거리로 목적지를 구하는 다익스트라 알고리즘을 여기서는 최소한의 거울로 문제를 풀면 된다. 보통의 그래프 탐색에 방향이 추가되어 현재 방향과 다른 방향으로 갈 경우 방향을 갱신하고 1을 더해주어야 한다.


map을 입력받으며 만들어둔 Node class를 사용하여 시작 레이저, 도착 레이저를 저장한다.
최초에는 모든 방향이 다 가능하므로 방향 변수는 -1로 저장한다.
동시에 추후 최소 거울의 수를 갱신할 visit배열을 무한대로 초기화한다.


우선순위 큐에서 최소 거울 Node를 꺼내 4방향 탐색하며 거울 수가 더 적은 경우 갱신하고 큐에 추가한다.
시간복잡도를 줄이기 위해 우선순위 큐를 사용한다.
최초 -1이거나 현재 방향과 탐색 방향이 다른경우 거울 수를 더한다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    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];
        int[][] visit = new int[H][W];

        Node start = null, end = null;

        for (int i = 0; i < H; i++) {
            String t = br.readLine();

            for (int j = 0; j < W; j++) {
                map[i][j] = t.charAt(j);
                visit[i][j] = Integer.MAX_VALUE;

                if (map[i][j] == 'C') {
                    if (start == null) {
                        start = new Node(i, j, -1, 0);
                    } else {
                        end = new Node(i, j, -1, 0);
                    }
                }
            }
        }

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.add(start);
        visit[start.x][start.y] = 0;

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

            if (cur.x == end.x && cur.y == end.y) break;

            for (int k = 0; k < 4; k++) {
                int nx = cur.x + dx[k];
                int ny = cur.y + dy[k];
                int ncnt = cur.cnt;

                if (nx < 0 || ny < 0 || nx >= H || ny >= W || map[nx][ny] == '*') continue;

                if (cur.dir != -1 && cur.dir != k) ncnt++;

                if (visit[nx][ny] >= ncnt) {
                    visit[nx][ny] = ncnt;
                    pq.add(new Node(nx, ny, k, ncnt));
                }
            }
        }

        System.out.println(visit[end.x][end.y]);
    }

    public static class Node implements Comparable<Node>{
        int x;
        int y;
        int dir;
        int cnt;

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

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