BOJ#9376 탈옥

BOJ#9376 탈옥

* 문제

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

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 J번

* 풀이

어려운 문제라고 생각합니다.

일단 맵을 상하좌우로 1칸씩 늘려줍니다.

 -> 이유 : 시도1 처럼 여러 시작점들을 어딘가에 저장해놓고 조사하는 것과, 외곽의 어느 한점을 시작점으로 잡고 조사하는 것은 차이가 없다.

(문이 아니라면 cost가 없기 때문)

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

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

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

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

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

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

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

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

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

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

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

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

아래의 예에서는 빨간색 박스로 표시된 문이 최소값입니다.

Sum 결과

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%239376_PrisonBreak/src/Main.java

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

/**
 * BOJ#9376 탈옥
 * https://www.acmicpc.net/problem/9376
 */

public class Main {

    static final int BLANK = 0;
    static final int WALL = -1;
    static final int PRISON = 1;
    static final int DOOR = 2;

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

    static int[][] map = new int[105][105];
    static int h, w;

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

        int t;

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

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

        while (t-- > 0) {

            // input
            Node helper = new Node(0, 0);
            Node prison1 = new Node(-1, -1);
            Node prison2 = new Node(-1, -1);

            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 '.':
                            map[i][j] = BLANK;
                            break;
                        case '*':
                            map[i][j] = WALL;
                            break;
                        case '$':
                            map[i][j] = PRISON;

                            if (prison1.row == -1) {

                                prison1 = new Node(i, j);
                            } else {

                                prison2 = new Node(i, j);
                            }
                            break;
                        case '#':
                            map[i][j] = DOOR;
                            break;
                    }
                }
            }

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

                map[0][j] = map[h - 1][j] = BLANK;
            }

            // 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] == WALL) continue;

                    tempCost = dist1[i][j] + dist2[i][j] + dist3[i][j];
                    if (map[i][j] == DOOR) tempCost -= 2;

                    ans = ans > tempCost ? tempCost : ans;
                }
            }

            System.out.println(ans);

        } // ~while loop

    } // ~main

    static int[][] bfs(Node src) {

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

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

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

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

        queue.add(src);
        dist[src.row][src.col] = 0;

        while (!queue.isEmpty()) {

            Node u = queue.poll();

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

                int nextRow = u.row + dRow[i];
                int nextCol = u.col + dCol[i];

                if (nextRow < 0 || nextRow >= h || nextCol < 0 || nextCol >= w) continue;
                if (map[nextRow][nextCol] == WALL) continue;
                //if (discovered[nextRow][nextCol]) continue;

                if (map[nextRow][nextCol] == BLANK || map[nextRow][nextCol] == PRISON) {

                    if (dist[nextRow][nextCol] == -1 || dist[nextRow][nextCol] > dist[u.row][u.col]) {

                        dist[nextRow][nextCol] = dist[u.row][u.col];
                        queue.add(new Node(nextRow, nextCol));
                    }
                } else if (map[nextRow][nextCol] == DOOR) {

                    if (dist[nextRow][nextCol] == -1 || dist[nextRow][nextCol] > dist[u.row][u.col] + 1) {

                        dist[nextRow][nextCol] = dist[u.row][u.col] + 1;
                        queue.add(new Node(nextRow, nextCol));
                    }
                }
            }
        }

        return dist;
    }

    static void printMap(int[][] arr) {

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

                System.out.printf("%4d", arr[i][j]);
            }
            System.out.println();
        }
    }
}

class Node {

    int row;
    int col;

    Node(int row, int col) {

        this.row = row;
        this.col = col;
    }
}