BOJ_6087_레이저 통신 (Java)

[Gold III] 레이저 통신 - 6087

문제 링크

성능 요약

메모리: 18580 KB, 시간: 168 ms

분류

너비 우선 탐색, 데이크스트라, 그래프 이론, 그래프 탐색, 최단 경로

제출 일자

2025년 1월 31일 14:49:56

문제 설명

크기가 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를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

문제 풀이

벽 부수고 이동하기와 비슷하다고 생각했으며, 거울에 대한 우선순위가 있기 때문에 다익스트라 문제라고 생각했다.

구현은 처음에는 int[][] 배열 visited를 사용한 기본적 다익스트라에 Node 클래스를 만들어 mirror개수에 대한 우선순위로 정렬하고자 했다. 하지만 이때 어떤 방향으로 특정 칸에 들어왔느냐에 따라 4가지 상태가 있는데, 이때 모든 경우의 수를 2차원 visited로 해결할 수가 없었다.

예를 들어 왼쪽으로 마무리 한 Node와 위쪽으로 마무리한 Node가 그때까지 사용한 거울의 개수가 차이날 때 거울 적게 쓴 방향을 골라야하지만 향후 미래를 생각해봤을 때 모든 경우의 수를 고려해야 한다는 점에서 visited를 4가지 방향을 고려한 3차원으로 만들어주었다.

코드

package BOJ_6087_레이저통신;
        
/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main{
    class Node implements Comparable<Node>{
        int r, c, direction, mirror;
        public Node(int r, int c, int direction, int mirror){
            this.r = r;
            this.c = c;
            this.direction = direction;
            this.mirror = mirror;
        }

        @Override
        public int compareTo(Node o){
            return this.mirror - o.mirror;
        }
    }
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int W, H;
    static char board[][];
    static int visited[][][];
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
    static List<int[]> C_List = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_6087_레이저통신/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        board = new char[H+2][W+2];
        visited = new int[H+2][W+2][4];

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

        for (int i = 1; i <= H; i++) {
            String str = br.readLine();
            for (int j = 1; j <= W; j++) {
                board[i][j] = str.charAt(j-1);
                if(board[i][j] == 'C') C_List.add(new int[]{i, j});
            }
        }

        int res = findMinMirror();
        
        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
        br.close();
    }

    private int findMinMirror() {
        int[] C_Start = C_List.get(0);
        int[] C_End = C_List.get(1);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(C_Start[0], C_Start[1], -1, 0));
        for(int k=0; k<4; k++){
            visited[C_Start[0]][C_Start[1]][k] = 0;
        }

        while(!pq.isEmpty()){
            Node currNode = pq.poll();
            if(currNode.r == C_End[0] && currNode.c == C_End[1]) return currNode.mirror;

            for(int k = 0; k < 4; k++){
                int[] nextPos = new int[]{currNode.r + dr[k], currNode.c + dc[k]};
                int currMirrorCnt = currNode.mirror;

                if(board[nextPos[0]][nextPos[1]] == '*') continue;

                if(currNode.direction != -1 && currNode.direction != k) currMirrorCnt++;

                if(currMirrorCnt < visited[nextPos[0]][nextPos[1]][k]) {
                    pq.offer(new Node(nextPos[0], nextPos[1], k, currMirrorCnt));
                    visited[nextPos[0]][nextPos[1]][k] = currMirrorCnt;
                }
            }
        }
        return -1;
    }
}