[백준 9376] 탈옥

회고

• map 이 주어지고, 이동을 해야 하는데 이동 횟수(depth) 제한이 없으면 BFS로 풀어야 함
  • 두 죄수의 이동 경로만을 생각하고 DFS로 풀기엔 depth 제한이 없다. 헐 
  • depth 제한이 없으면, BFS로 생각해보자.
• 생각의 틀을 깬 방식
  1. 죄수1 이 밖으로 나가는데 열어야 할 문의 최소 횟수
  2. 죄수2 가 밖으로 나가는데 열어야 할 문의 최소 횟수
  3. 조력자가 안으로 들어가기 위해 열어야 할 문의 최소 횟수
• 1, 2, 3 을 동시에 구하여 합이 최소인 경우가 답

  • 
    

풀이

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

문제

상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.

평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.

문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.

상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.

출력

각 테스트 케이스마다 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 최솟값을 출력한다.

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Arrays;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;

 

/**

 *

  죄수 2명을 탈옥시키는 방법은 3가지가 있습니다.

 1) 죄수 1이 죄수2를 데리고 바깥으로 나가는 경우

 2) 죄수2가 죄수1을 데리고 바깥으로 나가는 경우

 3) 외부의 조력자가 죄수1, 2를 찾으러 잠입하는 경우

 

    위 3가지 경우가 동시에 실행된다면?

    3명은 각자 문을 열면서 탐색을 할 것이고 어느 정점에서 만나게 될 것입니다.

    그리고 우리는 그 시점에 탈옥이 완료되었다고 볼 수 있을 것입니다.

     

    어느 정점에서 만나게 될지 모르니 맵의 모든 정점을 조사해야할테고

    각 정점마다 3명이 문을 몇개 열고 왔는지 합산을 해줍니다. 그리고 그 중 가장 최소값이 우리가 원하는 답이 될 것입니다.

    단, 만나는 지점이 문인 경우 -2를 해줘야 합니다.(3명이 동시에 문을 열지 않아도 된다.)

     

    정리하면, 위 3가지 BFS를 돌려 3개의 dist[][]를 완성시킨 후 sum을 해줍니다.

    각 정점마다 조사를 하면서 최소값을 구합니다. (단, 문의 위치인 경우 -2)

 */

 

public class Main {

    static final int[] nx = { 0, -1, 0, 1 };

    static final int[] ny = { -1, 0, 1, 0 };

 

    static int[][] map = new int[105][105];

    static int h, w;

 

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

 

        int t;

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

        while (t-- > 0) {

            Node2 helper = new Node2(0, 0);

            Node2 prison1 = null;

            Node2 prison2 = null;

 

            StringTokenizer st = new StringTokenizer(br.readLine());

 

            h = Integer.parseInt(st.nextToken()) + 2;

            w = Integer.parseInt(st.nextToken()) + 2;

 

            for (int i = 1; i < h - 1; i++) {

                String s = "." + br.readLine() + ".";

                for (int j = 0; j < w; j++) {

 

                    char c = s.charAt(j);

                    switch (c) {

 

                    case '.':

                    case '*':

                    case '#':

                        map[i][j] = c;

                        break;

                    case '$':

                        map[i][j] = c;

                        if (prison1 == null) {

                            prison1 = new Node2(i, j);

                        } else {

                            prison2 = new Node2(i, j);

                        }

                        break;

                    }

                }

            }

 

            for (int j = 0; j < w; j++) {

                map[0][j] = map[h - 1][j] = '.';

            }

 

            // solve

            int[][] dist1 = bfs(helper);

            int[][] dist2 = bfs(prison1);

            int[][] dist3 = bfs(prison2);

 

            int ans = h * w;

            int tempCost = 0;

            for (int i = 0; i < h; i++) {

                for (int j = 0; j < w; j++) {

                    if (map[i][j] == '*')

                        continue;

 

                    tempCost = dist1[i][j] + dist2[i][j] + dist3[i][j];

                    if (map[i][j] == '#')

                        tempCost -= 2;

 

                    ans = ans > tempCost ? tempCost : ans;

                }

            }

 

            System.out.println(ans);

        }

 

    }

 

    public static int[][] bfs(Node2 src) {

        int[][] dist = new int[h][w];

 

        for (int i = 0; i < h; i++) {

            Arrays.fill(dist[i], -1);

        }

 

        Queue<Node2> queue = new LinkedList<Node2>();

        queue.add(src);

        dist[src.x][src.y] = 0;

 

        while (!queue.isEmpty()) {

            Node2 u = queue.remove();

 

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

                int xx = u.x + nx[i];

                int yy = u.y + ny[i];

 

                if (xx < 0 || xx >= h || yy < 0 || yy >= w)

                    continue;

                if (map[xx][yy] == '*')

                    continue;

 

                if (map[xx][yy] == '.' || map[xx][yy] == '$') {

                    if (dist[xx][yy] == -1 || dist[xx][yy] > dist[u.x][u.y]) {

                        dist[xx][yy] = dist[u.x][u.y];

                        queue.add(new Node2(xx, yy));

                    }

                } else if (map[xx][yy] == '#') {

                    if (dist[xx][yy] == -1 || dist[xx][yy] > dist[u.x][u.y] + 1) {

                        dist[xx][yy] = dist[u.x][u.y] + 1;

                        queue.add(new Node2(xx, yy));

                    }

                }

            }

        }

 

        return dist;

    }

}

 

class Node2 {

    int x;

    int y;

 

    Node2(int x, int y) {

        this.x = x;

        this.y = y;

    }

}