코딩 테스트

방 탈출의 최소 시간

#POJ 3057 · 문제 원문 ↗ BFS · Bipartite matching · DFS · Binary search

POJ 3057 「Evacuation」은 벽으로 구분된 방의 사람들이 문마다 1초에 한 명씩 빠져나가는 문제입니다. X는 벽, .은 사람이 있는 빈칸, D는 문입니다. 매초 상하좌우로 한 칸 이동할 수 있고, 모두 나가는 최소 시간을 구합니다.

원문에서는 내부 한 칸에 여러 사람이 있을 수 있습니다. 제한은 문 통과에 적용됩니다. 문에 닿으면 이미 탈출했으므로 다른 구역으로 가는 통로로 쓰지 않습니다. 아래 재생은 사람의 이동 애니메이션이 아니라 문을 통과하는 시간표입니다.

INTERACTIVE LAB문과 시간에 사람 배정하기

현재 상태

풀이의 핵심

  1. BFS로 거리 구하기: 각 문에서 빈칸으로 탐색해 사람 p가 문 d에 도착하는 최소 시간 dist[d][p]를 구합니다.
  2. 시간 T로 질문 바꾸기: T초 안에 모두 탈출할 수 있는지 확인합니다. 오른쪽 정점은 (문, 1초), (문, 2초)…(문, T초)입니다.
  3. 이분 그래프 만들기: 사람 p는 dist[d][p] ≤ t인 (문 d, 시각 t) 슬롯에 연결됩니다. 도달 불가능한 문에는 연결하지 않습니다.
  4. DFS로 배정 조정하기: 슬롯이 이미 사용 중이면 기존 사람을 다른 슬롯으로 옮길 수 있는지 재귀적으로 찾습니다. 모든 사람이 서로 다른 슬롯을 얻으면 T초에 가능합니다.
  5. 최소 T 찾기: 가능한 T보다 큰 시간도 가능하므로 이분 탐색합니다.

여기서 DFS는 방 안의 이동 경로가 아니라 배정 그래프를 탐색합니다. 예를 들어 P1은 1초에 D1·D2 모두 가능하고 P2는 D1만 가능하다면, P1을 D1에 먼저 넣었어도 DFS로 P1→D2, P2→D1로 재배정할 수 있습니다.

문 1개 예제는 사람이 8명입니다. 가장 먼 사람의 최단거리는 5초지만, 문이 초당 한 명만 처리하므로 정답은 8초입니다. 「최소 시간 찾기」를 누른 뒤 T를 1 줄여 배정 인원이 어떻게 바뀌는지 확인하세요.

매칭 하나는 각 사람에게 도달 가능한 시각을 주고 문·시각의 중복을 막습니다. 내부에서 기다릴 수 있으므로 이 배정대로 탈출할 수 있습니다. 반대로 실제 탈출 일정도 이런 매칭이 되므로, 전원 매칭 여부와 T초 내 탈출 가능 여부가 일치합니다.

복잡도와 주의점

사람 수 P, 문 수 D, 지도 R × C, 가장 먼 사람의 가까운 문까지 거리를 L이라 합시다. 아무 문에도 도달하지 못하는 사람이 있으면 impossible입니다. 그 외에는 max(L, ceil(P/D))부터 U = L + P - 1까지 탐색합니다. 모두 L초 안에 가까운 문 앞에 도달한 뒤 최대 P명이 순서대로 나가면 U초면 충분합니다.

거리 계산은 O(DRC)입니다. T초 그래프의 간선 수를 ET라 하면 DFS 매칭 한 번은 O(P ET)이고 ET ≤ PDT입니다. 따라서 전체 시간 상한은 O(DRC + P EU log(U+1)), 추가 공간은 O(RC + DP + EU + DU)입니다.

가장 가까운 문으로만 보내거나 최장 최단거리만 답으로 쓰면 병목을 놓칩니다. 내부 칸에도 한 명 제한이 있는 다른 문제라면 이 모델은 적용되지 않습니다. 아래는 이 조건에 맞춰 작성한 C++ 풀이이며, 브라우저 실험은 작은 예제에 맞췄습니다.

직접 작성한 풀이 코드

C++ (C++98) 
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;

struct Evacuation {
    vector<pair<int, int> > people, doors;
    vector<vector<int> > distance, edges;
    vector<int> owner, seen;
    int stamp;

    bool augment(int person) {
        for (int i = 0; i < (int)edges[person].size(); ++i) {
            int slot = edges[person][i];
            if (seen[slot] == stamp) continue;
            seen[slot] = stamp;
            if (owner[slot] == -1 || augment(owner[slot])) {
                owner[slot] = person;
                return true;
            }
        }
        return false;
    }

    bool feasible(int limit) {
        int p = people.size(), d = doors.size();
        edges.assign(p, vector<int>());
        for (int person = 0; person < p; ++person)
            for (int door = 0; door < d; ++door)
                if (distance[door][person] != -1)
                    for (int t = distance[door][person]; t <= limit; ++t)
                        edges[person].push_back((t - 1) * d + door);
        owner.assign(d * limit, -1);
        seen.assign(d * limit, 0);
        stamp = 0;
        for (int person = 0; person < p; ++person) {
            ++stamp;
            if (!augment(person)) return false;
        }
        return true;
    }

    int solve(const vector<string>& grid) {
        int h = grid.size(), w = grid[0].size();
        for (int r = 0; r < h; ++r) for (int c = 0; c < w; ++c) {
            if (grid[r][c] == '.') people.push_back(make_pair(r, c));
            if (grid[r][c] == 'D') doors.push_back(make_pair(r, c));
        }
        int p = people.size(), d = doors.size();
        if (p == 0) return 0;
        if (d == 0) return -1;
        distance.assign(d, vector<int>(p, -1));
        int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
        for (int door = 0; door < d; ++door) {
            vector<vector<int> > dist(h, vector<int>(w, -1));
            queue<pair<int, int> > q;
            q.push(doors[door]);
            dist[doors[door].first][doors[door].second] = 0;
            while (!q.empty()) {
                int r = q.front().first, c = q.front().second;
                q.pop();
                for (int k = 0; k < 4; ++k) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
                    if (grid[nr][nc] != '.' || dist[nr][nc] != -1) continue;
                    dist[nr][nc] = dist[r][c] + 1;
                    q.push(make_pair(nr, nc));
                }
            }
            for (int person = 0; person < p; ++person)
                distance[door][person] = dist[people[person].first][people[person].second];
        }
        int farthest = 0;
        for (int person = 0; person < p; ++person) {
            int nearest = h * w + 1;
            for (int door = 0; door < d; ++door)
                if (distance[door][person] != -1)
                    nearest = min(nearest, distance[door][person]);
            if (nearest == h * w + 1) return -1;
            farthest = max(farthest, nearest);
        }
        int low = max(farthest, (p + d - 1) / d), high = farthest + p - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (feasible(mid)) high = mid;
            else low = mid + 1;
        }
        return low;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int cases;
    cin >> cases;
    while (cases--) {
        int h, w;
        cin >> h >> w;
        vector<string> grid(h);
        for (int r = 0; r < h; ++r) cin >> grid[r];
        Evacuation solver;
        int answer = solver.solve(grid);
        if (answer < 0) cout << "impossible\n";
        else cout << answer << '\n';
    }
}

참고 자료와 다음 실험