BOJ 1420 학교 가지마!

 

문제 링크 : https://www.acmicpc.net/problem/1420

1420번: 학교 가지마!

 

출발 정점(도현이의 위치)이나 도착 정점(학교)의 주변을 벽으로 막으면...

맵 모양에 관계없이 답은 4 이하임을 알 수 있다.  

따라서 등교를 막을 수 없는 경우를 체크할 때, 유량이 4를 초과하는 것을 이용할 수 있다.

 

 

하여간 4 이하인 값 찾기 위해 '유량 네트워크'를 써야 하다니?

다른 방법이 없을까 생각해 보아야겠다.

 

문제로 돌아가서 어떻게 모델링을 할 것인가를 생각해 보자.

 

최소의 개수로 벽을 세우면 학교를 못가게 만드는 정점들을 알고 있다고 가정하자.

정점들을 한 번만 이용할 수 있도록 모델링하면 가능한 경로 수가 차단에 필요한 정점의 개수와 일치하게 된다.

경로의 수는 정점을 분할하고 분할된 정점 사이의 간선의 용량을 1로 하면 최대 유량이 될 것이고...

 

위 내용을 다르게 표현하면 간선 용량이 1 일 때, Minimum Cut 을 찾는 문제가 된다는 얘기.

사실 분할된 정점 사이의 용량을 1로 두면 나머지 간선은 아무렇게나 두어도 된다.

그래서 도현이와 학교가 인접하는 경우를 따로 확인하기 귀찮아서

유량이 4를 초과하도록 다른 간선들은 큰 값의 capacity 를 적용했다.

 

#include<bits/stdc++.h>

using namespace std;

const int Inf=1e9;

char str[101][101];

struct MF{
    struct edge{ 
        int to, cap, rev;
    };
    
    int sz, Src, Ter;
    vector<vector<edge>> adj;
    vector<int> level, work;
    
    MF(int sz, int S, int T) : sz{sz}, Src{S}, Ter{T} {
        adj=vector<vector<edge>>(sz);
    };
    
    bool bfs(){
        level=vector<int>(sz, -1);
        level[Src]=0;
        queue<int> q;
        q.push(Src);
        
        while(!q.empty() && level[Ter]==-1){
            int cur=q.front();
            q.pop();
            for(int i=0;i<adj[cur].size();i++){
                edge te=adj[cur][i];
                int nxt=te.to;
                if(level[nxt]==-1 && te.cap>0){
                    level[nxt]=level[cur]+1;
                    if(nxt==Ter) break;
                    q.push(nxt);
                }
            }
        }
        return level[Ter]!=-1;
    }
    
    int dfs(int cur, int flow){
        if(cur==Ter) return flow;
        for(int &i=work[cur];i<adj[cur].size();i++){
            edge te=adj[cur][i];
            int nxt=te.to;
            if(level[nxt]==level[cur]+1 && te.cap>0){
                int f=dfs(nxt, min(flow, te.cap));
                if(!f) continue;
                
                adj[cur][i].cap-=f;
                adj[nxt][te.rev].cap+=f;
                
                return f;
            }
        }
        return 0;
    }
    
    int solve(){
        int tFlow=0;
        while(bfs()){
            work=vector<int>(sz,0);
            while(1){
                int flow=dfs(Src, Inf);
                if(!flow) break;
                tFlow+=flow;
            }
        }
        return tFlow;
    }
    
    void link(int u, int v, int cap){
        adj[u].push_back({v, cap, (int)adj[v].size()});
        adj[v].push_back({u, 0, (int)adj[u].size()-1});
    }
};

int main(){
    int n,m; scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%s", str[i]);
    
    MF mf(2*n*m, 0,1);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(str[i][j]=='#') continue;
            if(str[i][j]=='K')  mf.Src=2*(i*m+j)+1;
            if(str[i][j]=='H')  mf.Ter=2*(i*m+j);
            
            mf.link(2*(i*m+j), 2*(i*m+j)+1, 1);
            
            if(i<n-1 && str[i+1][j]!='#'){
                mf.link(2*(i*m+j)+1, 2*((i+1)*m+j), Inf);
                mf.link(2*((i+1)*m+j)+1, 2*(i*m+j), Inf);
            }
                       
            if(j<m-1 && str[i][j+1]!='#'){
                mf.link(2*(i*m+j)+1, 2*(i*m+j+1), Inf);
                mf.link(2*(i*m+j+1)+1, 2*(i*m+j), Inf);
            }
        }
    }
    
    int ans=mf.solve();
    if(ans>4) printf("-1\n");
    else printf("%d\n", ans);
}

 

굳이 한마디 첨언해 두자면

인접 리스트를 쓰면서 각 간선에 대해 역간선을 만들면

인접 행렬을 쓰는 경우와 달리 그래프가 simple 일 것을 강요하지 않는다.

따라서 가급적 인접 행렬를 쓰지 않는 쪽이 좋을 것이다.