문제

WN 크기에 지도에서 C로 표시된 두 칸은 레이저를 쏠 수 있는 칸이다. 빈 칸은 '.', 벽은 ''로 표시된다. 레이저를 발사하면서 거울을 설치해서 방향을 회전 시킬 수 있다. 이때 두 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 구하면 된다.

풀이

사용한 자료구조

• map : 전체 지도 (출발/도착점, 빈 칸, 벽)
  처음 입력받은 C를 출발점으로 잡고, 다음 C를 도착으로 정했다.
• visited : 해당 칸까지 필요한 최소 거울 수를 저장한다.
• laser : ArrayList에 출발, 도착점을 저장한다.

전체 흐름

1. 시작점(c1)에서 bfs()를 수행한다.
2. 도착점에 도착하면 bfs를 종료하는 게 아니라, count와 answer 중 최솟값을 저장한다.
   도착점에 최소 경로로 도착하는 경우가 거울의 수도 최소일거라는 보장이 없기 때문에 계속 탐색한다.
3. 이전 좌표와 현재 좌표의 방향이 바뀔 때 거울이 설치된다.
   C일 때의 dir은 -1이고, -1일 때는 거울을 설치하지 않는다.
4. visited에는 거울 설치의 최소값을 저장한다.

소스 코드

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

public class BOJ_6087 {
    static char[][] map;
    static int[][] visited;
    static ArrayList<Point> laser;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int W;
    static int H;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        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];
        visited = new int[H][W];
        laser = new ArrayList<>();

        for (int i = 0; i < H; i++) {
            String[] input = br.readLine().split("");
            for (int j = 0; j < W; j++) {
                visited[i][j] = Integer.MAX_VALUE; // 최대로 초기화

                char val = input[j].charAt(0);
                map[i][j] = val;

                if (val == 'C') {
                    laser.add(new Point(i, j, -1, 0));
                }
            }
        }

        bfs();
    }

    static void bfs() {
        Queue<Point> q = new LinkedList<>();

        Point c1 = laser.get(0); // 출발 레이저
        Point c2 = laser.get(1); // 도착 레이저

        q.add(c1);
        visited[c1.x][c1.y] = 0;

        while (!q.isEmpty()) {
            Point p = q.poll();

            int x = p.x; //현재 좌표
            int y = p.y;
            int dir = p.dir;
            int count = p.count;

            if (x == c2.x && y == c2.y) {
                answer = Math.min(count, answer);
            }

            // 0 : 북, 1 : 남, 2 : 서, 3: 동
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i]; //다음 좌표
                int ny = y + dy[i];
                int nd = i;

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

                // 이전 좌표의 방향과 현재 좌표의 방향 비교
                int temp = count;
                if (dir != nd && dir != -1) {
                    temp++;
                }

                if (visited[nx][ny] < temp) {
                    continue;
                }

                visited[nx][ny] = temp;
                q.add(new Point(nx, ny, nd, temp));
            }
        }
        System.out.println(answer);
    }

    static class Point {
        int x;
        int y;
        int dir;
        int count;

        public Point(int x, int y, int dir, int count) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.count = count;
        }
    }
}