백준 6087 - 레이저 통신(Java)

문제

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

예제 입력 1 복사

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

예제 출력 1 복사

3

 

풀이

문제 자체는 C에서 C까지 탐색하는 것, start와 end 를 찾아서 start를 PQ에 넣고 탐색을 진행하면 된다.

경우의 수를 줄이기 위해 visited 배열을 int형으로 선언 후, 해당 위치까지 도달하기 위한 거울의 갯수를 넣고, 탐색중에 비교해서 지금이 더 크면 해당 경우는 배제한다.

또한, 레이저가 어느 방향에서 오는지도 중요하기 때문에 3차원 배열로 해서 4방향에 따라 방문 배열의 값이 다르도록 해주었다. 방문 배열의 의미는 [~방향에서][i][j]번째에 도달할 때 필요한 거울의 갯수 이다.

탐색은 BFS로 진행했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ_6087_레이저통신 {
    public static class Node implements Comparable<Node> {
        int x,y;
        int cost;
        int dir;
        public Node(int x, int y, int cost,int dir){
            this.x = x;
            this.y = y;
            this.cost = cost;
            this.dir = dir;
        }

        @Override
        public int compareTo(Node other) {
            return this.cost - other.cost;
        }
    }
    static int W;
    static int H;
    static char[][] map;
    static int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};
    static Node start,end;

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

        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new char[H][W];
        boolean flag = false;
        for(int i=0; i<H; i++)
        {
            map[i] = br.readLine().toCharArray();
            for(int j=0; j<W; j++)
            {
                if(map[i][j]=='C')
                {
                    if(flag)
                        end = new Node(i,j,-1,-5);
                    else{
                        start = new Node(i,j,-1,-5);
                        flag = true;
                    }
                }
            }
        }
        int result = bfs();
        System.out.println(result);
    }

    public static int bfs()
    {
        int min = Integer.MAX_VALUE;
        PriorityQueue<Node> queue = 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);
            }
        }
        queue.offer(start);
        while(!queue.isEmpty())
        {
            Node temp = queue.poll();
            if(temp.x == end.x && temp.y == end.y)
            {
                min = Math.min(min,temp.cost);
                continue;
            }
            for(int dir=0; dir<4; dir++)
            {
                int nx = temp.x + deltas[dir][0];
                int ny = temp.y + deltas[dir][1];
                int next = (temp.dir==dir)?temp.cost:temp.cost+1;
                if(nx < 0 || H <= nx || ny < 0 || W <= ny || map[nx][ny]=='*'||Math.abs(temp.dir-dir)==2)
                    continue;
                if(visited[dir][nx][ny] > next) {
                    queue.offer(new Node(nx, ny, next, dir));
                    visited[dir][nx][ny] = next;
                }
            }
        }
        return min;
    }

}