백준 9376번 : 탈옥 [Java]

www.acmicpc.net/problem/9376

9376번: 탈옥

package 백준;

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 백준9376_탈옥 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st = null;
    //빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.

    static final char EMPTY = '.';
    static final char WALL = '*';
    static final char DOOR = '#';
    static final char PRISONER = '$';

    public static void main(String[] args)  throws IOException {
        int t;
        char[][] map;

        t = Integer.parseInt(br.readLine());

        for (int testCase = 0; testCase < t; testCase++)
        {
            int h, w, prisonerIdx, minimumOpenDoor;
            int[][] prisonerOne, prisonerTwo, sanggeun;

            st = new StringTokenizer(br.readLine());
            h = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            // h + 2 , w + 2 외부 출입라인 생성
            map = new char[h + 2][w + 2];
            Prisoner[] prisoners = new Prisoner[2];
            prisonerIdx = 0;

            String line = null;
            for (int i = 0; i < h; i++)
            {
                line = br.readLine();
                for (int j = 0; j < w; j++)
                {
                    map[i + 1][j + 1] = line.charAt(j);
                    if (line.charAt(j) == PRISONER)
                    {
                        prisoners[prisonerIdx++] = new Prisoner(i + 1, j + 1);
                    }
                }
            }

            prisonerOne = bfs(map, prisoners[0], h, w);
            prisonerTwo = bfs(map, prisoners[1], h, w);
            sanggeun = bfs(map, new Prisoner(0, 0), h, w);

            System.out.println();
            printMap(prisonerOne);
            printMap(prisonerTwo);
            printMap(sanggeun);

            minimumOpenDoor = getMinimumSum(prisonerOne, prisonerTwo, sanggeun, map);
            System.out.println(minimumOpenDoor);
        }
    }

    private static void printMap(int[][] arr)
    {
        for (int[] a: arr)
        {
            System.out.println(Arrays.toString(a));
        }
        System.out.println();
    }

    private static int getMinimumSum(int[][] prisonerOne, int[][] prisonerTwo, int[][] sanggeun, char[][] map) {
        int minSum;

        minSum = Integer.MAX_VALUE;

        for (int i = 0; i < prisonerOne.length; i++)
        {
            for (int j = 0; j < prisonerOne[i].length; j++)
            {
                if (map[i][j] == '*')
                    continue;

                int sum = prisonerOne[i][j] + prisonerTwo[i][j] + sanggeun[i][j];
                if (map[i][j] == '#')
                {
                    sum -= 2;
                }
                if (minSum > sum)
                {
                    minSum = sum;
                }
            }
        }


        return (minSum);
    }

    private static int[][] bfs(char[][] map, Prisoner prisoner, int h, int w) {
        PriorityQueue<Prisoner> queue = new PriorityQueue<>();
        boolean[][] visited = new boolean[h + 2][w + 2];
        int[][] doorHistory = new int[h + 2][w + 2];

        queue.add(prisoner);
        visited[prisoner.x][prisoner.y] = true;

        while (!queue.isEmpty())
        {
            Prisoner temp = queue.poll();
            doorHistory[temp.x][temp.y] = temp.openDoor;

            for (int i = 0; i < 4; i++)
            {
                int nx, ny;

                nx = temp.x + dx[i];
                ny = temp.y + dy[i];
                if (0 <= nx && nx < h + 2 && 0 <= ny && ny < w + 2 && !visited[nx][ny]
                && map[nx][ny] != '*')
                {
                    visited[nx][ny] = true;
                    queue.add(new Prisoner(nx, ny, map[nx][ny] == '#' ? temp.openDoor + 1 : temp.openDoor));
                }
            }
        }
        return (doorHistory);
    }

    static int[] dx = {0, 0 ,1, -1};
    static int[] dy = {1, -1 ,0, 0};


    public static class Prisoner implements Comparable<Prisoner>{
        int x, y, openDoor;

        public Prisoner(int x, int y) {
            this.x = x;
            this.y = y;
            this.openDoor = 0;
        }

        public Prisoner(int x, int y, int openDoor) {
            this.x = x;
            this.y = y;
            this.openDoor = openDoor;
        }

        @Override
        public int compareTo(Prisoner o) {
            return Integer.compare(this.openDoor, o.openDoor);
        }
    }
}

 

빠르게 문제의 요지를 파악하고 넘어가자.

 

고려할 것은 문을 어떻게 문제에서 제시하는 두 명의 죄수, 한 명의 외부인이 문을 어떻게 열 것인가? 이다.

 

풀이를 찾아보는 많은 이들이 분명히 BFS를 사용한다는 개념은 이해했을 것이라 생각한다.

 

하지만 이들을 한번에 움직일 것인가? 아니면 각자 움직일 것인가? 고려해보아야 한다.

 

해설은 다음과 같다.

 

1. 죄수1이 움직인다.
2. 죄수2이 움직인다.
3. 외부인이 움직인다.

자, 그럼 각자 움직이면서 BFS로 탐색을 하게 된다면, 최소 거리로 문을 여는 개수를 배열에 저장할 수 있을 것인다.

 

[출처] https://rebas.kr/770

[출처] https://rebas.kr/770

위와 같이, 각자가 움직이면서 각 지점에서 최소로 열어온 문의 개수를 기록할 수 있다.

 

그럼 모든 배열의 각 위치에서 합산을 한다.

 

여기서 합산의 의미는 특정 위치까지 세 명이 문을 열어온 개수를 확인한다는 것이다.

 

따라서, 전체 배열을 순회하면서 비교한다면, 만났을 때 문을 열어온 최소 개수를 구할 수 있을 것인다.

 

여기서 두 가지 주의해야 한다.

 

첫 번째, 합산하는 위치에 문이 있다면 3명 중에 한명만 열면 되기 때문에 -2를 해준다.

두 번째, BFS로 각 인원들을 움직여 줄 때, 우선 순위 큐로 문을 가장 적게 연 사람을 우선적으로 탐색시켜야 한다.