BOJ G3 6087 레이저 통신 JAVA

6087번: 레이저 통신

---

문제 풀기

이 문제에서 보통의 맵 문제와 다른 점은 거울이다. 하지만 거울의 개수는 그냥 이동 방향의 변화 횟수를 카운트하면 되기 때문에 그것만 떠올리면 그리 어렵진 않다.

 

처음에 딱 읽었을 때는 BFS가 생각났다. BFS로 이동하면서 이동 방향이 이전과 바뀌면 카운트를 하면 되지 않을까? 생각했다. 그리고 재방문이 안 된다는 걸 고려해서 순회하는 방향을 계속 바꿔주는 식으로 문제를 풀었다.

그렇게 BFS로 풀고 제출했더니 3퍼센트에서 틀렸다.

 

그래서 뭐지.. 하면서 분류를 봤는데 다익스트라가 있었다..!

 

다익스트라로 어떻게 하지? 하고 문제를 가만히 보다가, 거울 개수의 최솟값을 해야 했다. 즉 ‘최소 비용’ 문제인 것이다.

그래도 BFS를 할 때 최소를 찾도록 했는데, 어떤 게 차이가 있는 걸까? 싶었는데, 아무래도 BFS는 재방문이 안되는 것 때문에 생긴 문제인 것 같다.

 

다익스트라와 BFS의 차이점이라고 한다면, 다익스트라는 큐에서 뺄 때만 방문 체크를 하고, 방문했던 곳이라도 비용이 갱신되면 갱신해주고 큐에 다시 넣어주기 때문에 최소 비용을 찾는 이 문제에 더 적합한 것으로 보인다.

 

그래서 아래와 같이 다익스트라로 문제를 해결했다!

---

코드

package ps.ㄱSolving;

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

public class BOJ_G3_6087_레이저통신 {
    static class Pos{
        int r, c;
        int preDir;
        int changeCnt;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
        public Pos(int r, int c, int preDir, int changeCnt){
            this.r = r;
            this.c = c;
            this.preDir = preDir;
            this.changeCnt = changeCnt;
        }
    }
    static int H, W;
    static char[][] map;
    static Pos start = null, end = null;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new char[H][W];
        for (int i = 0; i < H; i++){
            map[i] = in.readLine().toCharArray();
            for (int j = 0; j < W; j++){
                if (map[i][j] == 'C'){
                    if (start == null) start = new Pos(i, j);
                    else end = new Pos(i, j);
                }
            }
        }

        int[][][] dist = new int[4][H][W];
        for (int di = 0; di < 4; di++){
            for (int i = 0; i < H; i++){
                Arrays.fill(dist[di][i], INF);
            }
            dijkstra(di, dist[di]);
        }
        System.out.println(
                Math.min(dist[0][end.r][end.c],
                        Math.min(dist[1][end.r][end.c],
                                Math.min(dist[2][end.r][end.c], dist[3][end.r][end.c])))
        );
    }
    static int INF = Integer.MAX_VALUE - 100;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static void dijkstra(int startDi, int[][] dist){
        //pq, dist, visited
        PriorityQueue<Pos> pq = new PriorityQueue<>(new Comparator<Pos>() {
            @Override
            public int compare(Pos o1, Pos o2) {
                return o1.changeCnt - o2.changeCnt;
            }
        });
        boolean[][] visited = new boolean[H][W];
        pq.offer(new Pos(start.r, start.c, startDi, 0));
        dist[start.r][start.c] = 0;

        while(!pq.isEmpty()){
            Pos cur = pq.poll();
            if (visited[cur.r][cur.c]) continue;

            visited[cur.r][cur.c] = true;
            for (int di = 0; di < 4; di++){
                int curDi = (di + startDi) % 4;
                int nr = cur.r + dr[curDi];
                int nc = cur.c + dc[curDi];
                if (nr < 0 || nr >= H || nc < 0 || nc >= W || map[nr][nc] == '*') continue;

                int cost = (cur.preDir != curDi)? 1 : 0;
                if (dist[nr][nc] > dist[cur.r][cur.c] + cost){
                    dist[nr][nc] = dist[cur.r][cur.c] + cost;
                    pq.offer(new Pos(nr, nc, curDi, dist[nr][nc]));
                }
            }
        }
    }
}