백준 9376 탈옥

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

9376번: 탈옥

이 문제는 공부 삼아 블로그를 참고해서 풀었다 (https://stack07142.tistory.com/145 님 블로그)
정말 혼자서는 생각도 못 해낼 방법인 듯...
많이 배웠다!

기본

• 기본적으로 이 문제에서 가중치는 연 문의 개수이다 (Pos 객체의 door변수로 체크)
• visit 배열을 방문/미방문이 아니라 몇 개의 문을 열어 해당 지점에 도착했는지를 기록한다
• 더 적은 가중치(연 문의 수)로 해당 지점을 재방문할 수 있을 때에만 큐에 넣어준다

여기까지는 일반적인 BFS와 동일하다

심화

• 일반 BFS로 풀면 시간초과가 난다!
• 문제에 힌트가 있는데, 죄수 2명 외에 상근이라는 외부인이 존재한다 => 이 친구를 player에 집어 넣는다
• map을 넓혀서 테두리를 모두 '.'으로 채우고 (0,0)에 상근이가 위치한다고 가정한다
• 상근이와 죄수2명 각각 BFS를 돌린다 (총 3번의 BFS)
• BFS는 visit기록을 리턴하고 이 기록을 각각의 배열에 저장한다
• 각 배열의 요소를 더한 게 최소가 되는 지점을 찾는다 => 답

예외처리

• 만약 셋이 문에서 만나게 될 경우 열어야 할 문은 하나인데 +3이 되어버린다 => 답에서 -2를 해줘야 한다

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Pos {
        int x, y, door;

        public Pos(int x, int y, int door) {
            super();
            this.x = x;
            this.y = y;
            this.door = door;
        }

        @Override
        public String toString() {
            return "Pos [x=" + x + ", y=" + y + ", door=" + door + "]";
        }

    }

    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static char[][] map = new char[105][105];
    static int h, w;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            h = Integer.parseInt(st.nextToken()) + 2;
            w = Integer.parseInt(st.nextToken()) + 2;

            List<Pos> player = new ArrayList<Main.Pos>();
            player.add(new Pos(0, 0, 0));
            for (int i = 1; i < h - 1; i++) {
                map[i][0] = '.';
                map[i][h - 1] = '.';
                String input = br.readLine();
                for (int j = 1; j < w - 1; j++) {
                    map[i][j] = input.charAt(j - 1);
                    // System.out.println(i+", "+j);
                    // System.out.println(Arrays.toString(map[i]));
                    if (map[i][j] == '$') {
                        player.add(new Pos(i, j, 0));
                    }
                }

            }

            for (int j = 0; j < w; j++) {
                map[0][j] = map[h - 1][j] = '.';
            }
            int[][] dist1 = bfs(player.get(0));
            int[][] dist2 = bfs(player.get(1));
            int[][] dist3 = bfs(player.get(2));

            int ans = Integer.MAX_VALUE;
            int sum = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == '*')
                        continue;
                    sum = dist1[i][j] + dist2[i][j] + dist3[i][j];
                    if (map[i][j] == '#')
                        sum -= 2;
                    ans = Math.min(ans, sum);
                }
            }
            System.out.print(ans + "\n");
        }
    }

    static int[][] bfs(Pos start) {
        int[][] visit = new int[h][w]; // 몇 개의 문을 열었는지 기록
        Queue<Pos> q = new LinkedList<Pos>();
        memset(visit, -1);
        visit[start.x][start.y] = 0;
        q.offer(start);

        while (!q.isEmpty()) {
            Pos now = q.poll();
            int x = now.x;
            int y = now.y;
            int door = now.door;
            //System.out.println(x + ", " + y);
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int ndoor = door;
                if (nx < 0 || nx > h - 1 || ny < 0 || ny > w - 1)
                    continue;
                if (map[nx][ny] == '*')
                    continue;
                if (map[nx][ny] == '#') { // 문일 경우
                    ndoor++;
                }
                if (visit[nx][ny] == -1 || visit[nx][ny] > ndoor) {
                    visit[nx][ny] = ndoor;
                    q.offer(new Pos(nx, ny, ndoor));
                }
            }
        }

        return visit;
    }

    static void memset(int[][] arr, int val) {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                arr[i][j] = val;
            }
        }
    }
}