[BOJ] 9376. 탈옥

[작성일]

• 2022-02-24

[분류]

• 다익스트라
• bfs
  
  
  

[문제링크]

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

[요구사항]

• 가장 문을 적게 열고 2명의 죄수 모두 탈출할 수 있는 경우를 구하라.
  
  
  

[풀이]

우선, 이 문제는 굉장히 어려웠다. 처음에 bfs를 써야한다는 느낌은 있었는데 3명의 bfs를 따로 수행하고 합한다는 생각은 전혀 생각하지 못해서 어려웠다. 그리고 이후, 다익스트라를 이용해서도 풀 수 있는 것을 보고 다시 풀어보았다.

1) bfs를 이용한 풀이
우선 상근이, 죄수1, 죄수2가 각각 bfs를 수행하여 밖으로 나가는 것을 수행한다. 이 때, 나가는 과정에서 문을 마주치는 경우 그 문을 열기 때문에 배열에 (이전에 문을 연 횟수 + 1)을 넣어준다. bfs를 수행할 때 큐는 우선순위 큐를 사용해서 일반적으로 거리기준으로 빨리 나가는 것이 아니라 문을 연 횟수가 가장 작은 것부터 꺼내서 경로를 탐색하도록 하는 것이 관건이다.

이렇게 되면 3개의 2차원 배열이 만들어진다.

여기서 가장 적게 문을 여는 경우는 무엇일까? 바로 3명이 만나는 지점에서 세 명이 문 연 횟수의 합이다.

• 상근이
• 죄수1
• 죄수2

모든 배열 칸에 대해서 3명의 문 연 횟수를 더해준다. 이 때 그 점이 문에 해당하는 경우에는 -2를 해줘야한다. 그 문에서 만났다는 말은 곧 3명이 동시에 그 문을 열었다는 의미인데 사실 1명만 열면 되기 때문이다.

이제 배열을 순회하며 최소 값을 출력하면된다. 그런데, 여기서도 중요한 것이 3명이 무조건 모두 방문한 점이어야 한다는 것이다. '.'에 해당하지만 갈 수 있는 길이 없어 방문하지 못한 경우, 당연히 배열은 0으로 차있을 것이기 때문에 제외하고 생각해주어야 한다.

2) 다익스트라를 이용한 풀이
다음에 마저 해보아야겠다.

[코드 - bfs]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};
    static int T, R, C;
    static int[][] prisoner1;
    static int[][] prisoner2;
    static int[][] sanggeun;
    static char[][] map;
    static int sx1, sy1, sx2, sy2;
    static boolean[][] visited;

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

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            // 바깥을 위해서 map을 더 크게 만든다
            map = new char[R + 2][C + 2];
            // map 가장자리는 빈공간으로 채운다
            Arrays.fill(map[0], '.');
            for (int i = 1; i <= R; i++) {
                map[i][0] = '.';
                map[i][C + 1] = '.';
            }
            Arrays.fill(map[R + 1], '.');

            // map 초기화
            int prisonerCnt = 0;
            for (int i = 1; i <= R; i++) {
                String s = br.readLine();
                for (int j = 1; j <= C; j++) {
                    map[i][j] = s.charAt(j - 1);
                    if (map[i][j] == '$') {
                        if (prisonerCnt == 0) {
                            sx1 = i;
                            sy1 = j;
                            prisonerCnt++;
                        } else if (prisonerCnt == 1) {
                            sx2 = i;
                            sy2 = j;
                        }
                    }
                }
            }

            // 3명의 사람에 대해서 bfs
            prisoner1 = bfs(sx1, sy1);
            prisoner2 = bfs(sx2, sy2);
            sanggeun = bfs(0, 0);

            // 칸에 있는 지나온 문의 갯수(열쇠사용횟수)를 다 더하고 최소값인 것을 정답으로 한다
            // 이 때 그 칸이 문일 경우 만나는 지점에서 3명이 동시에 문을 연 것이기 때문에 -2를 해준다.
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < R + 2; i++) {
                for (int j = 0; j < C + 2; j++) {
                    if(!visited[i][j]) continue;
                    if(map[i][j] == '*') continue;
                    int sum = sanggeun[i][j] + prisoner1[i][j] + prisoner2[i][j];

                    if (map[i][j] == '#') sum -= 2;
                    ans = Math.min(ans, sum);
                }
            }
            sb.append(ans + "\n");
        }
        System.out.println(sb);
    }

    public static int[][] bfs(int sx, int sy) {
        int[][] openCnt = new int[R + 2][C + 2];
        visited = new boolean[R + 2][C + 2];
        PriorityQueue<Point> pq = new PriorityQueue<>();
        pq.add(new Point(sx, sy, 0));
        openCnt[sx][sy] = 0;
        visited[sx][sy] = true;

        while (!pq.isEmpty()) {
            Point p = pq.poll();

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if (!isBorder(nx, ny) && !visited[nx][ny] && map[nx][ny] != '*') {
                    visited[nx][ny] = true;

                    if (map[nx][ny] == '#') {
                        pq.add(new Point(nx, ny, p.openCnt + 1));
                        openCnt[nx][ny] = p.openCnt + 1;
                    } else {
                        pq.add(new Point(nx, ny, p.openCnt));
                        openCnt[nx][ny] = p.openCnt;
                    }
                }
            }
        }
        return openCnt;
    }

    public static boolean isBorder(int x, int y) {
        return (x < 0 || y < 0 || x > R + 1 || y > C + 1);
    }

    public static class Point implements Comparable<Point> {
        int x;
        int y;
        int openCnt;

        public Point(int x, int y, int openCnt) {
            this.x = x;
            this.y = y;
            this.openCnt = openCnt;
        }

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