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

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

 

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

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

---

1.  아이디어

 

각 위치에 대해 거울의 설치 횟수를 최소로 하며 도착할 수 있는지 판단하는 방식으로 다익스트라 알고리즘을 활용했다.

---

2. 문제풀이

 

다익스트라 알고리즘에 활용할 노드 클래스는 위치와 방향, 거울 설치 횟수를 필드로 갖고 거울 설치 횟수에 대한 정렬 기준을 설정했다. 방문 체크와 거리 배열의 경우 위치 뿐만 아니라 방향에 대한 체크도 해줘야 했는데 같은 거울 설치 횟수로 도착해도 레이저의 방향이 다르면 이후 결과가 달라질 수 있기 때문이다. 시작 위치에서 모든 방향으로 레이저를 쏜 후 사방탐색을 하며 사방탐색 방향과 현재 레이저 방향이 일치하는지 90도 차이가 나는지에 따라 구분해서 구현하면 됐다. 다익스트라 종료 후 도착점에 대해 모든 방향에서 최소 거울 설치 횟수를 구한 후 반환하도록 구현했다.

---

3. 코드

 

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

public class Main {

    // 지도에서 위치와 방향, 해당 위치까지 가는데 사용한 거울 개수를 갖는 노드 클래스
    private static class Node implements Comparable<Node> {
        int r;
        int c;
        int dir;
        int cnt;

        public Node(int r, int c, int dir, int cnt) {
            this.r = r;
            this.c = c;
            this.dir = dir;
            this.cnt = cnt;
        }

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

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    private static final int INF = 1_000_000_000;

    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());

        Queue<int[]> pos = new ArrayDeque<>();
        char[][] map = new char[H][W];
        for (int i = 0; i < H; i++) {
            map[i] = br.readLine().toCharArray();

            for (int j = 0; j < W; j++) {
                if (map[i][j] == 'C') pos.add(new int[]{i, j});
            }
        }

        int min = dijkstra(pos.remove(), pos.remove(), H, W, map);
        System.out.println(min);
    }

    private static int dijkstra(int[] start, int[] end, int H, int W, char[][] map) {
        // 시작 위치에서 모든 방향으로 레이저 출발
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start[0], start[1], 0, 0));
        pq.add(new Node(start[0], start[1], 1, 0));
        pq.add(new Node(start[0], start[1], 2, 0));
        pq.add(new Node(start[0], start[1], 3, 0));

        // 위치와 해당 위치로 온 레이저 방향에 대한 방문 체크 배열
        boolean[][][] visited = new boolean[H][W][4];

        // 다익스트라 알고리즘의 거리 배열
        int[][][] cntMap = new int[H][W][4];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                Arrays.fill(cntMap[i][j], INF);
            }
        }
        cntMap[start[0]][start[1]][0] = 0;
        cntMap[start[0]][start[1]][1] = 0;
        cntMap[start[0]][start[1]][2] = 0;
        cntMap[start[0]][start[1]][3] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.remove();

            // 도착점이면 레이저 이동 종료
            if (node.r == end[0] && node.c == end[1]) continue;

            if (visited[node.r][node.c][node.dir]) continue;
            visited[node.r][node.c][node.dir] = true;

            for (int dir = 0; dir < 4; dir++) {
                int nr = node.r + dr[dir];
                int nc = node.c + dc[dir];

                if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
                if (map[nr][nc] == '*' || visited[nr][nc][dir]) continue;

                // 현재 레이저 방향과 이동할 방향이 같은 방향인 경우
                if (node.dir == dir) {
                    if (cntMap[nr][nc][dir] > cntMap[node.r][node.c][node.dir]) {
                        cntMap[nr][nc][dir] = cntMap[node.r][node.c][node.dir];
                        pq.add(new Node(nr, nc, dir, cntMap[nr][nc][dir]));
                    }
                }
                // 현재 레이저 방향과 이동할 레이저 방향이 직각인 경우
                else if ((node.dir + 1 + 4) % 4 == dir || (node.dir - 1 + 4) % 4 == dir) {
                    if (cntMap[nr][nc][dir] > cntMap[node.r][node.c][node.dir] + 1) {
                        cntMap[nr][nc][dir] = cntMap[node.r][node.c][node.dir] + 1;
                        pq.add(new Node(nr, nc, dir, cntMap[nr][nc][dir]));
                    }
                }
            }
        }

        // 도착점에 온 레이저 방향에 대해 최솟값 반환
        return Math.min(Math.min(cntMap[end[0]][end[1]][0], cntMap[end[0]][end[1]][1]), Math.min(cntMap[end[0]][end[1]][2], cntMap[end[0]][end[1]][3]));
    }

}

---

4. 후기