[백준] 6087 : 레이저 통신(JAVA), 다익스트라

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

6087번: 레이저 통신

 

방향을 회전시킨다기에 시뮬레이션 문제인가 싶어서 삽질을 했다.
결론적으로 C에서 C까지 최소 개수의 거울(최소비용)을 사용하는 경로를 찾는 다익스트라 문제였다.
기본적으로 다익스트라를 적용시키되, 주의해야할 점은 (x,y) 지점에 오기 까지 사용한 비용(거울의 수)가 같더라도 직전 방향에 따라 다음 지점에서의 비용이 달라지기 때문에 같은 비용까지는 우선순위 큐에 넣어주어야 한다는 점이다.

4 6
.C..
....
....
**.*
....
...C

위의 테스트 케이스가 앞서 말한 경우다.
(0,1) 지점의 C에서 출발한다고 할 경우 (2,2) 지점을 향하는 경로 두가지를 살펴보자.

/* 1번 경로 (ㄴ자)*/
4 6
.C..
.|..
.\-.
**.*
....
...C

/*2번 경로 (ㄱ자)*/
4 6
.C\.
..|.
..|.
**.*
....
...C

(2,2) 지점 기준, 1번 경로로 오든 2번 경로로 오든 거울을 1개씩만 사용하여 비용이 같다.
하지만 비용이 같다고 1번 경로만 우선순위 큐에 추가할 경우 (3,2) 지점에서 문제가 생긴다.
1번 경로는 직전 방향이 → 였기 때문에 (3,2)로 향하려면 추가로 거울이 필요한 반면, 2번 경로의 경우 직전 방향이 ↓ 기 때문에 추가로 거울이 필요하지 않다.
때문에 비용이 같은 경우 까지 큐에 추가해준다.

class Pos implements Comparable<Pos> {
    int x, y, dir, cost;

    public Pos(int x, int y, int dir, int cost) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.cost = cost;
    }

    @Override
    public int compareTo(Pos o) {
        return this.cost - o.cost;
    }
}

큐에 넣을 Pos 클래스는 위와 같다.

• x, y : 행과 열
• dir : 직전 방향
  • -1은 시작 지점 C를 뜻한다
  • 0 - 북, 1 - 서, 2 - 남, 3 -동 (방향 배열(dirX, dirY)의 인덱스로 활용된다.)
• cost : (x,y) 지점에 오기까지 사용한 거울의 수

public class P6087 {
    static char[][] arr;
    static int[][] cost; //필요한 최소 거울 수 저장
    static int[] dirX = {-1, 0, 1, 0}; //북, 서, 남, 동
    static int[] dirY = {0, -1, 0, 1};
    static int H, W;

    public static int bfs(int x, int y) {
        PriorityQueue<Pos> q = new PriorityQueue<>();
        q.add(new Pos(x, y, -1, 0));
        cost[x][y] = 0;

        int cnt = 0;

        while (!q.isEmpty()) {
            Pos tmp = q.poll();
			
            // 두번째 C(종료지점)와 만날 경우 종료
            if (arr[tmp.x][tmp.y] == 'C') {
                cnt++;
                if (cnt == 2) return cost[tmp.x][tmp.y];
            }
            if (tmp.cost > cost[tmp.x][tmp.y]) continue;

            for (int i = 0; i < 4; i++) {
                int nx = tmp.x + dirX[i];
                int ny = tmp.y + dirY[i];

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

				// 직전 방향과 달라질 경우 && 출발점이 아닐 경우
                if (i != tmp.dir && tmp.dir != -1) {
                    if (cost[nx][ny] >= tmp.cost + 1) {
                        cost[nx][ny] = tmp.cost + 1;
                        q.add(new Pos(nx, ny, i, tmp.cost + 1));
                    }
                // 직전 방향과 같을 경우
                } else {
                    if (cost[nx][ny] >= tmp.cost) {
                        cost[nx][ny] = tmp.cost;
                        q.add(new Pos(nx, ny, i, tmp.cost));
                    }
                }
            }
        }
        return -1;
    }

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

        arr = new char[H][W];
        cost = new int[H][W];

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                cost[i][j] = Integer.MAX_VALUE;
            }
        }

        int startX = 0;
        int startY = 0;

        for (int i = 0; i < H; i++) {
            String input = br.readLine();
            for (int j = 0; j < W; j++) {
                arr[i][j] = input.charAt(j);
                if (arr[i][j] == 'C') {
                    startX = i;
                    startY = j;
                }
            }
        }
        System.out.println(bfs(startX, startY));
    }
}