[백준]#6087 레이저 통신

문제

크기가 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

풀이

이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 풀 수 있었다.

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

public class Main {
    static int N;
    static int M;
    static char[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};     // 위, 아래, 왼쪽, 오르쪽 좌표 진행을 위한 

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        map = new char[N][M];
        Pair start = null;

        for(int i=0; i<N; i++) {
            String str = br.readLine();

            for(int j=0; j<M; j++) {
                map[i][j] = str.charAt(j);
                if(map[i][j]=='C' && start==null) {
                    start = new Pair(i, j, 0, 0);
                    map[i][j] = '*';
                }
            }
        }
        bfs(start);
    }

    public static void bfs(Pair start) {
        PriorityQueue<Pair> queue = new PriorityQueue<>();      //최소 거울 수가 낮으면 먼저 가도록 하기 위해서 우선순위 큐 사용
        boolean[][][] visited = new boolean[N][M][4];           //각 방향과 좌표의 중복 체크를 위한 배열
        for(int i=0; i<4; i++)
            queue.add(new Pair(start.x, start.y, i,0));

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            if(map[temp.x][temp.y]=='C') {
                System.out.println(temp.cnt);
                break;
            }

            int nx = temp.x+dx[temp.d];
            int ny = temp.y+dy[temp.d];
            int nd = temp.d;

            if(nx<0 || nx>=N || ny<0 || ny>=M || visited[nx][ny][nd] || map[nx][ny]=='*') continue;   //예외상황(벽이거나 좌표밖이거나 방문했던 좌표)

            visited[nx][ny][nd] = true;
            queue.add(new Pair(nx, ny, nd, temp.cnt));

            if(nd==0) {                                                 //각각 방향마다 거울 사용하는 경우
                queue.add(new Pair(nx, ny, 2, temp.cnt+1));
                queue.add(new Pair(nx, ny, 3, temp.cnt+1));
            }

            else if(nd==1) {
                queue.add(new Pair(nx, ny, 2, temp.cnt+1));
                queue.add(new Pair(nx, ny, 3, temp.cnt+1));
            }

            else if(nd==2) {
                queue.add(new Pair(nx, ny, 0, temp.cnt+1));
                queue.add(new Pair(nx, ny, 1, temp.cnt+1));
            }

            else {
                queue.add(new Pair(nx, ny, 0, temp.cnt+1));
                queue.add(new Pair(nx, ny, 1, temp.cnt+1));
            }
        }
    }

    public static class Pair implements Comparable<Pair>{         //x : row 좌표, y : column, d : 방향, cnt : 거울 
        int x;
        int y;
        int d;
        int cnt;

        public Pair(int x, int y, int d, int cnt) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.cnt = cnt;
        }

        public int compareTo(Pair p) {
            return this.cnt > p.cnt ? 1 : -1;
        }
    }
}