[Baekjoon,1420] 학교 가지마!

이 문제는 각 위치를 정점으로 하고 시작 위치를 소스, 도착 위치를 싱크라고 했을 때 최소 컷을 구하면 되므로 최대 유량 최소 컷 정리 에 따라 최대 유량을 구하면 된다. 그런데 무작정 칸들에 대해 최대유량을 구하면 벽이 칸들을 잇는 길에 놓일 수 있다. 이때 간선을 막는 것이 아닌 정점, 즉 벽을 놓았을 때 칸이 막혀야 하는 것이기 때문에 각 정점을 둘로 쪼개야 한다. 이 방법으로 길이 아닌 한 칸에 벽을 놓아야 하는 것을 해결할 수 있다.

용량은 다음과 같이 설정한다. 둘로 쪼개어진 정점의 간선만 용량을 1로 설정하고 모든 길은 마음껏 지나갈 수 있기 때문에 길을 잇는 간선의 용량은 무한대로 한다. 증가 경로를 찾는 중 역방향 유량의 계산을 위해서 반대 방향의 용량은 0으로 설정한다.

최적화

1. 각 정점에 연결된 간선이 얼마 없다.

각 위치에는 상,하,좌,우 네 가지의 방향이 연결되어 있을 수 있다. 이 때문에 flow를 인접 행렬로 구현하면 이용 되지 않는 간선이 너무 많아 메모리가 낭비된다. 이는 메모리 초과 라는 결과를 일으킨다. 이것을 해결하는 방법은 두 정점을 key 값으로 하고 현재 유량을 value로 한 map을 생성하는 것이다.

2. 쪼개진 정점의 용량의 크기는 1이다.

이를 이용하여 용량을 따로 구현하지 않고 유량만을 이용하여 구현 할 수 있다. 유량이 1이 된 경우 이미 유량이 다 찬 것으로 생각할 수 있으며 용량이 무한대인 경우에는 해당 유량을 음의 무한대로 설정하면 된다. 이러한 최적화는 쪼개진 정점의 용량의 크기가 1로 고정되어 있기 때문에 할 수 있다.

구현

각 위치에 대응되는 정점 번호를 구하는 함수를 만들어 구현한 것을 볼 수 있다.

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
using namespace std;

const int NEG_INF=-987654321;
const int MAX_V=20002;
const int OUT=10000;

const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};

int N,M,SRC,SNK;
vector<int> adj[MAX_V];
map<pair<int,int>,int> flow;

inline bool inRange(int y, int x)
{
    return 0<=y && y<N && 0<=x && x<M;
}

// 각 정점을 위치에 대응 시킨다.
inline int convert(int y, int x)
{
    return y*M+x;
}

void setGraph(const vector<string>& map)
{
    for(int y=0;y<N;++y)
        for(int x=0;x<M;++x)
        {
            if(map[y][x]=='#')
                continue;
            int here=convert(y,x);
            // 쪼개진 정점은 In -> Out 으로 이어져 있다. 
            // 역방향으로 흐르는 유량이 있을 수 있으니 
            // 반대쪽 정점도 추가하여야 한다. 
            adj[here].push_back(here+OUT);
            adj[here+OUT].push_back(here);
            
            flow[{here,here+OUT}]=0;
            flow[{here+OUT,here}]=1;
            for(int dir=0;dir<4;++dir)
            {
                int ny=y+dy[dir];
                int nx=x+dx[dir];
                if(inRange(ny,nx) && map[ny][nx]!='#')
                {
                    int there=convert(ny,nx);
                    
                    adj[here+OUT].push_back(there);
                    adj[there].push_back(here+OUT);
                    
                    flow[{here+OUT,there}]=NEG_INF;
                    flow[{there,here+OUT}]=1;
                }
                
                if(map[y][x]=='K')
                {
                    SRC=here;
                    flow[{here,here+OUT}]=NEG_INF;
                }
                else if(map[y][x]=='H')
                {
                    SNK=here;
                    flow[{here,here+OUT}]=NEG_INF;
                }
            }
        }
}

int getMinBlock()
{
    int totalFlow=0;
    int V=N*M*2;
    while(true)
    {
        queue<int> q;
        vector<int> parent(MAX_V,-1);
        q.push(SRC);
        parent[SRC]=SRC;
        // BFS로 증가경로를 찾는다. 
        while(!q.empty() && parent[SNK]==-1)
        {
            int here=q.front();
            q.pop();
            for(int i=0;i<adj[here].size();++i)
            {
                int there=adj[here][i];
                if(parent[there]==-1 && flow[{here,there}]<1)
                {
                    parent[there]=here;
                    q.push(there);
                }
            }
        }
        // 더 이상 증가 경로를 찾을 수 없을 때 
        if(parent[SNK]==-1)
            break;
        // 증가 경로에 유량을 흘려 보낸다.
        for(int p=SNK;p!=SRC;p=parent[p])
        {
            flow[{parent[p],p}]++;
            flow[{p,parent[p]}]--;
        }
        ++totalFlow;
    }
    return totalFlow;
}

bool canStop()
{
    if(SRC-M==SNK || SRC+M==SNK || 
       (abs(SRC-SNK)==1 && SRC/M==SNK/M))
        return false;
    return true;
}

int main()
{
    vector<string> map;
    cin>>N>>M;
    for(int i=0;i<N;++i)
    {
        string s;
        cin>>s;
        map.push_back(s);
    }
    
    setGraph(map);
    if(canStop())
        cout<<getMinBlock()<<endl;
    else
        cout<<-1<<endl;
    
    return 0;
}