골드에그

1. 문제요약

9376번: 탈옥 (acmicpc.net)

W x H 크기의 직사각형 감옥이 있다. 이 감옥에는 두 명의 죄수가 있는데 이 두 죄수를 탈출시키기 위해서 열어야 하는 문의 최소 개수값은 얼마인지 구하시오. 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다. 문은 한 번 열리면 계속 열린 상태가 된다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다. (죄수 - 감옥 - 죄수 모두 연결 상태)

2. 문제예제

3. 팩트추출

Fact 1 : Dijkstra 알고리즘 문제처럼 보인다. 그런데 출발지가 두 군데이고, 두 군데에서 같이 움직이면 BFS 의 경로 정보가 변질되어 버린다. [Programmers] 등산 코스 정하기 (Java) :: 골드에그 (tistory.com) 문제 같은 경우는 어디서 출발하던지 산봉우리에 도달하는 최소 경로만 찾으면 되므로 같이 움직여도 상관 없지만, 이 문제는 두 사람이 같은 경로로 탈출해야 한다는 점이 다르다.

같이 움직일 수 없다면 따로 움직여서 정보를 합쳐야 하는데 어떤 정보를 기준으로 합쳐야 할까?

어떠한 지점에서 BFS 최소 결과 값을 합친다면, 그 의미는 두 사람이 그 지점으로 만나기 위한 최소 값이다.

위 예제에서는 A 에서 1 로 가는 최소의 경로가 1 이고 B 에서 1 로 가는 최소의 경로가 2 인 것이다. A 와 B 가 만나기 위한 최소 값이라고 해석할 수 있다. 그런데 이 정보만으로는 부족하다. 탈출하기 위한 루트가 포함되지 않았다. A 와 B 는 만났지만, 탈출하기 위한 최소값이라고 볼 수는 없다.

탈출하기 위한 경로를 계산하려면, 탈출구에서 해당 지점까지 가는 경로도 추가해야 한다.

모든 경로가 최소가 되려면, A 에서 1 지점까지 거리도, B 에서 1 지점까지 거리도, 1 지점에서 탈출구까지 거리도 모두 최소여야 하기 때문이다. 만나는 지점을 중심으로 생각해보면 쉽다.

Fact 2 : 탈출구에 대한 정보를 맵 입력을 받을 때 알 수 없으므로 원래 맵 크기보다 1사이즈 더 크게 만들어 탈출구에서 오는 길목을 만들어준다. 원래 맵 크기가 N X M 이라면 N+2 X M+2 크기의 맵에서 시작한다.

Fact 3 : 정보를 합칠 때 중요한 점은 중복 정보를 제거해야 한다는 것이다. 1 지점까지 가는데 어떤 정보들이 중복이 되는지 생각해보아야 한다. 지문에서 문이 한 번 열리면 계속 열린 상태가 된다고 하였으므로 세 정보를 합칠 때 문에서 중복 카운트는 빼주어야 한다. 여기서는 세 명이 만난다고 가정해도 되므로 -2 를 해주면 된다.

4. 문제풀이(수동)

위 팩트추출을 통해 알아본 알고리즘으로 첫 번째 예제를 풀어보면 다음과 같다.

5. 문제전략

문제 전략은 팩트 추출과 문제 풀이를 통해 알아보았다. 원래 맵 크기보다 한 사이즈 큰 맵을 준비하고, 탈출구에서 오는 최소 DFS 결과 값과 각 죄수들로부터 DFS 한 결과 값을 합쳐 최소 경로를 구한다.

6. 소스코드

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

public class Main {
    private static int row, column;
    private static char[][] map;
    private static Node[] prisoners;
    private static final int[] dx = { 0, 0, -1, 1 };
    private static final int[] dy = { 1, -1, 0, 0 };
    private static final char WALL = '*';
    private static final char DOOR = '#';
    private static final char PRISONER = '$';
    static class Node implements Comparable<Node>{
        int x, y, open;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
            this.open = 0;
        }
        Node(int x, int y, int open) {
            this.x = x;
            this.y = y;
            this.open = open;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.open, o.open);
        }
    }
    private static int[][] bfs(Node start) {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        int[][] visited = new int[row+2][column+2];
        for (int[] visit: visited) {
            Arrays.fill(visit, -1);
        }

        queue.offer(start);
        visited[start.x][start.y] = 0;

        while(!queue.isEmpty()) {
            Node current = queue.poll();
            for (int i = 0; i < 4; i++) {
                int neighborX = current.x + dx[i];
                int neighborY = current.y + dy[i];
                if(neighborX < 0 || neighborX >= row+2 || neighborY < 0 || neighborY >= column+2) continue;
                if(visited[neighborX][neighborY] != -1 || map[neighborX][neighborY] == WALL) continue;
                if(map[neighborX][neighborY] == DOOR) {
                    visited[neighborX][neighborY] = visited[current.x][current.y] + 1;
                    queue.offer(new Node(neighborX, neighborY, current.open + 1));
                } else {
                    visited[neighborX][neighborY] = visited[current.x][current.y];
                    queue.offer(new Node(neighborX, neighborY, current.open));
                }
            }
        }
        return visited;
    }
    private static int getSum(int[][] one, int[][] two, int[][] out) {
        int minSum = row * column;

        for (int i = 0; i < one.length; i++)
        {
            for (int j = 0; j < one[i].length; j++)
            {
                if (map[i][j] == WALL)
                    continue;
                if (one[i][j] == -1 && two[i][j] == -1 && out[i][j] == -1)
                    continue;
                int sum = one[i][j] + two[i][j] + out[i][j];
                if (map[i][j] == DOOR)
                {
                    sum -= 2;
                }
                if (minSum > sum)
                {
                    minSum = sum;
                }
            }
        }
        return (minSum);
    }

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

        while(testCase-- > 0) {
            st = new StringTokenizer(br.readLine());
            row = Integer.parseInt(st.nextToken());
            column = Integer.parseInt(st.nextToken());
            map = new char[row+2][column+2];
            int[][] prisonerOne, prisonerTwo, out;
            prisoners = new Node[2];
            int prisonersIndex = 0;

            for (int i = 0; i < row; i++) {
                char[] row = br.readLine().toCharArray();
                for (int j = 0; j < column; j++) {
                    if (row[j] == PRISONER) {
                        prisoners[prisonersIndex++] = new Node(i + 1, j + 1);
                    }
                    map[i+1][j+1] = row[j];
                }
            }
            out = bfs(new Node(0,0));
            prisonerOne = bfs(prisoners[0]);
            prisonerTwo = bfs(prisoners[1]);
            System.out.println(getSum(prisonerOne, prisonerTwo, out));
        }
    }
}