[백준 1420번] [네트워크 플로우 / 정점 분할] 학교 가지마!

백준 2316번 도시 왕복하기 2 문제와 매우 유사하다.(viyoung.tistory.com/160)

 

이 문제를 보고 최소 컷 문제라는 것을 인식할 수 있다.

 

다만, 일반적인 최소것 문제의 경우에는 간선을 자르는데 이 문제는 정점을 잘라야 한다.

 

즉, 정점에 capacity를 줘서 처리하는 정점 분할 기법을 사용한 뒤 최소 컷을 구해주면 된다.

 

또한 Max flow Min cut Theorem에 의하여 이 문제는 다시 최대 유량 문제로 돌려서 구해주면 된다.

 

다만, 정점 분할을 진행할 경우에 주의해야할 지점은 source와 sink를 처리함에 있어서 매우 주의해야 한다.

(53번째 줄에서 예외처리해준 사항에 대해서 매우 주의하도록 하자.)

 

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
const int MAX_N = 20002;
int N, M;

struct edge{
    int from, to, capacity, flow;
    edge* reverse_edge;
    edge(int u, int v, int c) : from(u), to(v), capacity(c), flow(0)
    {}
    int residual(){
        return capacity - flow;
    }
    void add_flow(int amount){
        flow += amount;
        reverse_edge -> flow -= amount;
    }
};

vector<edge*> adj[MAX_N];

void add_edge(int u, int v, int c, bool dir = true){
    edge* e1 = new edge(u, v, c);
    edge* e2 = new edge(v, u, dir ? 0 : c);
    e1 -> reverse_edge = e2;
    e2 -> reverse_edge = e1;
    adj[u].push_back(e1);
    adj[v].push_back(e2);
}

int networkFlow(int source, int sink){
    int max_flow = 0;
    while(true){
        vector<edge*> parent(MAX_N, nullptr);
        queue<int> q;
        q.push(source);
        while(!q.empty() && parent[sink] == nullptr){
            int here = q.front(); q.pop();
            for(int i = 0; i < adj[here].size(); i++){
                int there = adj[here][i] -> to;
                if(adj[here][i] -> residual() > 0 && parent[there] == nullptr){
                    q.push(there);
                    parent[there] = adj[here][i];
                }
            }
        }
        if(parent[sink] == nullptr) break; // Fail to finding Augmenting path
        // 어차피 capacity는 1이므로 최소 residual 구하는 과정은 생략^^
        for(int p = sink; p != source; p = parent[p] -> from){
            // source와 sink는 정점분할하지 말아야 한다.(1번만 지나갈 수 있는 상황이 아니다)
            if(p != sink && p != source + 1) parent[p] -> add_flow(1);
        }
        max_flow++;
    }
    return max_flow;
}

bool available(int i, int j, int dir){
    // 오른쪽 체크
    if(dir == 0){
        if(j + 1 < M) return true;
        else return false;
    }
    else{
        if(i + 1 < N) return true;
        else return false;
    }

}

int main(void){
    fastio;
    cin >> N >> M;
    int source, sink;
    string data_store[N];

    if(N == 1 && M == 1){
        cout << -1 << "\n";
        return 0;
    }

    for(int i = 0; i < N; i++){
        string temp;
        cin >> temp;

        data_store[i] = temp;
    }

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

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            bool check_value = true;
            if(data_store[i][j] == 'K') source = i * M + j;
            else if(data_store[i][j] == 'H') sink = i * M + j;
            else if(data_store[i][j] == '#') continue;
            else check_value = false;
            // 오른쪽 체크
            if(available(i, j, 0)){
                if(data_store[i][j + 1] != '#'){
                    add_edge((i * M + j) * 2 + 1, (i * M + j + 1) * 2, 1);
                    add_edge((i * M + j + 1) * 2 + 1, (i * M + j) * 2, 1);

                    if(check_value == true && data_store[i][j + 1] != '.'){
                        cout << "-1\n";
                        return 0;
                    }
                }   
            }
            if(available(i, j, 1)){
                if(data_store[i + 1][j] != '#'){
                    add_edge((i * M + j) * 2 + 1, ((i + 1) * M + j) * 2, 1);
                    add_edge(((i + 1) * M + j) * 2 + 1, (i * M + j) * 2, 1);
                    if(check_value == true && data_store[i + 1][j] != '.'){
                        cout << "-1\n";
                        return 0;
                    }
                }
            }
        }
    }
    cout << networkFlow(source * 2, sink * 2 + 1) << "\n";
    return 0;
}