[백준/BOJ C++] 1420번 : 학교 가지마! (최대 유량 최소 컷 정리, 맵의 연결리스트 구현)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1420번 : '학교 가지마!' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘(Network Flow)와 최대 유량 최소 컷 정리(MFMC)에 대한 이해가 필요합니다.

 

 

1420번 : 학교 가지마!

1420번: 학교 가지마!

 

N형 M열의 지도가 주어졌을 때, K가 H까지 이동하지 못하도록 세워야 하는 벽('#')의 최소 수를 구하는 문제입니다.

문제 형태 자체는 이전에 풀었던 Gold V 난이도의 '연구소' 문제와 비슷하지만, 그것은 브루트포스 알고리즘으로 해결이 가능한 문제였고 여기서는 벽을 몇 개 세울지 알 수 없기 때문에 일일이 검사해서는 제한 시간 안에 풀이할 수 없습니다.

 

이 문제의 경우 잘 생각해보면 그래프 사이의 연결을 끊어 단절시킨다는 점에서 최소 컷 문제로 연결지어서 생각할 수 있습니다.

따라서 노드 사이의 유량을 구현해주고, 최대 유량 = 최소 컷이라는 MFMC 정리를 이용하여 문제를 해결할 수 있습니다.

그럼 최대 유량 최소 컷 정리를 이용하여 문제를 풀이해보겠습니다.

 

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 25000
#define INF 1000000000
using namespace std;

struct Edge {
    int From, To, Capacity, Flow;
    Edge* Rev;
    Edge(int U, int V, int C) : From(U), To(V), Capacity(C), Flow(0) {}
    int Remain() { return Capacity - Flow; }
    void AddFlow(int Amount) {
        Flow += Amount;
        Rev->Flow -= Amount;
    }
};
vector<Edge*> Line[MAX];

void AddLine(int From, int To, int Capacity) {
    Edge* E = new Edge(From, To, Capacity);
    Edge* RevE = new Edge(To, From, 0);
    E->Rev = RevE, RevE->Rev = E;
    Line[From].push_back(E), Line[To].push_back(RevE);
}

int MaxFlow(int Sour, int Sink) {
    int FlowSum = 0;
    while(true) {
        vector<Edge*> Prev(MAX, nullptr);
        queue<int> Queue;
        Queue.push(Sour);

        while(!Queue.empty()) {
            int Curr = Queue.front(); Queue.pop();
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i]->To;
                if(Line[Curr][i]->Remain() > 0 && Prev[Next] == nullptr) {
                    Queue.push(Next);
                    Prev[Next] = Line[Curr][i];
                }
            }
        }
        if(Prev[Sink] == nullptr) break;

        for(int i=Sink; i!=Sour; i=Prev[i]->From)
            if(i != Sink && i != Sour+1) Prev[i]->AddFlow(1);
        FlowSum++;
    }
    return FlowSum;
}

int main() {
    int N, M, Sour, Sink, Exit = 0;
    scanf("%d %d\n", &N, &M);

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) AddLine((i*M+j)*2, (i*M+j)*2+1, 1);

    char Map[101][101];
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            Map[i][j] = getchar();
            if(Map[i][j] != '.' && Map[i][j] != '#'
               && ((j > 0 && Map[i][j-1] != '.' && Map[i][j-1] != '#')
                   || (i > 0 && Map[i-1][j] != '.' && Map[i-1][j] != '#'))) Exit = 1;
            else if(Map[i][j] == 'K') Sour = (i*M+j)*2+1;
            else if(Map[i][j] == 'H') Sink = (i*M+j)*2;
        }
        getchar();
    }
    if(Exit) {
        printf("-1");
        return 0;
    }
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(Map[i][j] == '#') continue;
            if(j+1 < M && Map[i][j+1] != '#') {
                AddLine((i*M+j)*2+1, (i*M+j+1)*2, 1);
                AddLine((i*M+j+1)*2+1, (i*M+j)*2, 1);
            }
            if(i+1 < N && Map[i+1][j] != '#') {
                AddLine((i*M+j)*2+1, ((i+1)*M+j)*2, 1);
                AddLine(((i+1)*M+j)*2+1, (i*M+j)*2, 1);
            }
        }
    }
    printf("%d", MaxFlow(Sour, Sink));
}

 

최대 유량 최소 컷 정리는 사실 MaxFlow 함수 내에서 최대 유량을 구하는 것이 전부이므로, 네트워크 플로우에 대해 알고 있다면 크게 어렵지 않지만 문제는 Line[A][B]를 일일이 연결한다면 메모리 초과와 시간 초과가 발생한다는 것입니다.

 

이 문제의 경우에는 노드 사이의 연결이 무작위로 일어나는 것이 아니라, 좌표계에서 x좌표와 y좌표가 ±1인 인접한 좌표 사이에만 연결이 되어있기 때문에, 연결 리스트를 이용하여 인접한 좌표 사이의 노드끼리만 연결하여 메모리를 아끼도록 구현할 수 있습니다.

 

Edge에 대한 struct를 선언해주고, 여기에 Rev라는 이전 Edge도 선언하여 양방향으로 Edge들에 대한 탐색이 가능하도록 구현해줍니다.

E->Rev = RevE로, RevE->Rev = E로 양쪽으로 연결해주는 과정도 수행해줍니다.

 

맵을 입력받는 과정에서, 문제를 해결할 수 없는 유일한 경우는 K와 H가 인접하여 붙어있는 경우이므로, 입력을 받으면서 동시에 왼쪽이나 위쪽 칸에 K나 H가 인접하여 붙어있는지 검사해주고 만약 그렇다면 입력만 다 받고 바로 종료할 수 있도록 해줍니다.

입력이 끝난 후 다시 한 번 반복문을 돌리면서 오른쪽 좌표나 아래쪽 좌표에 벽이 없고 빈 칸이 연결되어 있다면, 두 좌표 사이에는 이동이 가능하므로 두 노드 사이를 연결해줄 수 있도록 합니다.

 

하나의 노드를 둘로 분할하여 두 노드 사이의 유량을 1로 설정하여 노드의 방문을 count 하는 기법은 이전에도 여러 번 다루었기 때문에 여기서는 크게 언급하지 않도록 하겠습니다.

어쨌든 위의 테크닉을 모두 종합하여 활용하면, MaxFlow 함수를 호출하여 최대 유량을 구할 수 있고 이것은 결국 최소 컷과 동일하므로 정답을 얻을 수 있습니다.