[백준] 9376번 : 탈옥

9376번: 탈옥

[Dijkstra * 3]

발상의 전환이 필요한 문제라고 생각된다. 문제에서 죄수 2명이 등장하여 이 2명이 여는 문의 개수를 세려고 하니, 잡아야 할 문제점이 잡히지 않았다. 그래서 여러 사람들이 사용한 제 3의 인물을 등장시켜 3명이 문을 여는 것으로 문제를 풀었다.

 

죄수 2명은 감옥 안에 주어지고, 제 3의 인물 상근이는 (0, 0)에서 시작한다. 이 3명은 모두 다익스트라 (BFS로 해도 무관하다고 생각됨)를 이용해 모든 문을 열고, 각 지점마다 몇 개의 문을 열고 왔는지를 기록한다.

 

각 지점마다 3명이 문을 연 개수를 더해 만약 그 지점이 문('#')이라면 -2를 한다. 문은 한 번만 열리면 되므로, 3명이 모두 열 필요는 없다. 그리고 중요한 것을 놓칠 수 있는데,

.	*	.
*	.	*
.	*	.

가운데 벽으로 둘러쌓인 공간이 있다. 이 때 이곳을 주의해야 하는데, 보통 다익스트라를 이용하면 처음에 distance를 INF로 초기화 한다. 근데 저 곳은 도달할 수 없으므로 INF * 3 = 음수가 나와 잘못된 답이 나올 수 있으므로, 3명이 문을 연 개수를 구할 때 그 값이 음수라면 skip하도록 한다.

# Code </>

public class Main {

    static class Point{
        int y, x;
        public Point(int yy, int xx){
            y=yy; x=xx;
        }
    }
    static class Edge implements Comparable<Edge>{
        Point p;
        int d, from;

        public Edge(Point p, int dist, int from){
            this.p=p;
            d=dist;
            this.from = from;
        }
        @Override
        public int compareTo(Edge o) {
            return d-o.d;
        }
    }

    static boolean[][][] visit;

    static char[][] map;
    static int[][][] distance;

    static Point[] prisoner;
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};

    static final int INF = 1000000000;
    static int h, w;

    static void Dijkstra(Point p1, Point p2){

        Queue<Edge> Q = new PriorityQueue<>();

        visit[0][0][0] = true;
        visit[p1.y][p1.x][1] = true;
        visit[p2.y][p2.x][2] = true;

        distance[0][0][0] = 0;
        distance[p1.y][p1.x][1] = 0;
        distance[p2.y][p2.x][2] = 0;

        Q.add(new Edge(new Point(0, 0) ,0, 0));
        Q.add(new Edge(p1, 0, 1));
        Q.add(new Edge(p2, 0, 2));

        while(!Q.isEmpty()){
            Edge edge = Q.poll();
            Point p = edge.p;
            int y = p.y;
            int x = p.x;
            int d = edge.d;
            int from = edge.from;

            if(distance[y][x][from] < d) continue;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 0 || nx < 0 || ny > h+1 || nx > w+1 || visit[ny][nx][from] || map[ny][nx] == '*') continue;

                int nextD = d;

                if(map[ny][nx] == '#')
                    nextD++;

                if(distance[ny][nx][from] > nextD){
                    visit[ny][nx][from] = true;
                    distance[ny][nx][from] = nextD;
                    Q.add(new Edge(new Point(ny, nx), nextD, from));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());

        for(int i=0; i<k; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int N = 102;
            h = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            visit = new boolean[N][N][3];
            map = new char[N][N];
            distance = new int[N][N][3];
            prisoner = new Point[2];

            int s = 0;
            for(int j=1; j<=h; j++){
                char[] str = br.readLine().toCharArray();
                for(int z=1; z<=w; z++){
                    map[j][z] = str[z-1];

                    if(map[j][z] == '$')
                        prisoner[s++] = new Point(j, z);
                }
            }
            for(int j=0; j<=h+1; j++)
                for(int z=0; z<=w+1; z++)
                    for(int x=0; x<3; x++)
                        distance[j][z][x] = INF;

            Dijkstra(prisoner[0], prisoner[1]);

            int min = INF;

            for(int a=1; a<=h; a++)
                for(int b=1; b<=w; b++){
                    if(map[a][b] == '*') continue;
                    int total = 0;
                    for(int c=0; c<3; c++)
                        total += distance[a][b][c];

                    if(total < 0) continue;

                    if(map[a][b] == '#') total -= 2;
                    min = Math.min(min, total);
                }

            System.out.println(min);
        }
    }
}