[백준] No.1420 - 학교 가지마! (C++, 최소 컷, 최대 유량, 정점 분할)

문제

 

https://www.acmicpc.net/problem/1420

1420번: 학교 가지마!

 

풀이

 

solved.ac 난이도: Platium 2

 

 

최소 컷 (최대 유량)알고리즘에 정점 분할을 적용해야 하는 문제.

 

정점 분할이란 정점에도 간선처럼 가중치를 주기 위해 정점을 하나의 간선으로 만드는 기법이다.

이때 간선을 정점처럼 취급하기 위해 정점을 두개의 정점(in과 out)으로 분할 한다.

in정점은 해당 정점으로 들어오는 간선들과 연결해주고

out정점은 해당 정점에서 다른 정점으로 나가는 간선을 연결해 준다.

 

다음과 같은 그래프를 정점 분할하여 표현하면 다음과 같다.

 

기존의 그래프

 

 

in과 out으로 정점 분할

 

 

문제를 해결하기 위해서는 유량을 흘리기 위해 한번 찾아진 증가 경로의 정점들은 이용하지 않는 것이다.

이를 위해 in -> out 간선의 가중치(용량)를 모두 1로 설정해주면 해당 정점에는 1 이상의 유량이 흐를 수 없으므로 사용된 정점은 더 이상 지나갈 수 없으므로 경로에 포함되지 않는다.

 

정점 분할에 이용한 in->out 간선 이외의 간선들은 모두 유량을 INF로 설정하여 얼마든지 유량을 흐를 수 있게 만들어주자.

실제 간선이 없는 역 방향 간선은 유령 간선으로, 유량을 0으로 설정하여 생성해준다.

(만약 아직 유령 간선과 간선의 용량에 대해서 잘 모른다면 다음 게시글을 먼저 읽고 오자.)

[네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘

 

따라서 정점 u에서 v로의 간선과 v에서 u로의 간선이 있는 경우 정점 분할 시 다음과 같이 표현된다.

 

 

 

 

여기서 왜 in -> out 간선의 가중치(용량)는 1로 설정해야 하는 걸까?

이를 이해하기 위해서는 최소 컷 정리를 알아야 한다.

 

최소 컷 문제는 간선 중 일부를 제거하여 source에서 sink로 가는 경로를 없애는데, 제거한 간선들의 가중치 합을 최소로 만드는 문제이다.

그래프의 최소 컷은 최대 유량과 같다는 것이 알려져 있다. 

 

이번 문제에서 source에서 sink로의 증가 경로를 없애는 것은 해당 경로를 더 이상 이용하지 못하도록 벽을 세우는 것과 같다.

하나의 최대 유량의 경로를 없애는 데는 벽 하나로도 충분 한데, 그 이유는 최소 컷으로 설명할 수 있다.

아래와 같은 도시의 입력이 주어진다고 생각해보자.

 

 

이를 최대 유량 알고리즘을 적용시키기 위해 벽을 제외한 인접 간선끼리 이어주면 다음과 같은 그래프가 나온다.

 

이러한 그래프에 정점 분할을 적용하여 K(source)에서 H(sink)로의 최대 유량을 찾는다면 중간의 정점을 지날 수밖에 없다.

 

 

이 그래프의 최소 컷을 찾는다면 중간의 정점의 in->out 간선의 가중치가 될 것이다.

(해당 간선만 자르면 source에서 sink로의 경로를 최소 cost로만으로 없앨 수 있다.)

즉, 이 in->out간선의 가중치를 1로 설정하여 최대 유량(최소 컷)을 구하면 최소 몇 개의 정점을 막아야 source에서 sink로의 모든 경로를 막을 수 있는지 구할 수 있다.

따라서 정점 분할을 적용한 그래프에 K에서 H로의 최대 유량을 구하면 된다.

 

단, 구현 시 정점의 개수 최대 10,000개로 많지만, 정점은 네 방향의 네 정점들과만 이어져있어 비교적 적을 편이다.

정점(u, v)끼리의 연결관계를 2차원 배열 adj[u][v]로 모두 저장한다면 메모리 초과는 물론 시간 초과까지 발생한다.

따라서 인접 리스트로 해당 정점의 간선만 저장해 주자.

 

인접 리스트로 최대 유량 알고리즘은 구현한다면 역방향 간선의 flow를 변경해 주기 위해 다음과 같은 구조체를 사용하였다.

 

struct Edge{
  int to, capacity,flow;
  Edge* reverse;    //역방향 간선의 포인터를 저장
 
  Edge(int _to, int _cap, int _flow =0) : to(_to) , capacity(_cap) {}
 
  int ResidualCapacity() const{
    return capacity - flow;
  }
 
  void PushFlow(int amount){    //유량을 흘려주면 역방향도 같이 변경
    flow += amount;
    reverse->flow -=amount;
  }
};
 
vector<vector<Edge*>> adj; //해당 정점에 연결된 간선을 저장

 

 

 

 

 

이번 문제를 풀 때 다음과 같은 입력에서도 어떻게 최소 컷을 올바르게 계산할 수 있는지 궁금해서 생각해본 내용을 조금 더 추가해 보겠다.

 

 

위와 같은 그래프에서 다음과 같이 첫 증가 경로가 찾아졌다면 모든 in -> out의 용량은 1이기 때문에 다른 경로는 파란 경로의 정점들을 지나가지 못하는 것 아닐까?

첫 증가 경로

다른 경로가 못 지나가는 게 아닐까?

이는 최대 유량을 찾는 포드-풀커슨 알고리즘이 유량의 대칭성을 위해 실제로 간선이 없는 역방향 간선에도 용량이 0인 유령 간선을 추가해 주기 때문에 가능하다.

 

첫 증가 경로에서 녹색 범위의 정점들만 그래프로 나타내 보자.

녹색 범위만 생각해 보자!

 

 

유량이 흐르게 된 실제 간선인 파란 간선에는 +1의 유량이

역방향의 유령 간선인 빨간 간선들에는 -1의 유량이 흐른다.

따라서 빨간 간선의 잔여 용량(= 용량 - 유량)은 +1(=0 -(-1))이 된다.

그러므로 유령 간선에도 1의 유량을 흘릴 수 있다.

 

다시 증가 경로를 찾는다면 다음과 같은 경로가 찾아진다.

이러한 경우는 어떻게 가능한 걸까?

 

위의 그래프에서 (3,1)의 in에서 (2,1)의 out으로의 유령 간선을 생각해보자.

이 간선은 잔여 용량이 1로 1의 유량을 흘려보내는 경로에 추가될 수 있다.

따라서 정점 분할 그래프에서 새로운 경로를 녹색으로 표현하면 다음과 같이 나타난다.

 

 

(3,1)의 in에서 (2,1)의 out으로의 유령 간선에  +1의 유량을 흘렸기 때문에 해당 간선의 잔여 용량은 0이 되고

역방향 간선인 실제 간선 (2,1) out에서 (3,1) in으로의 간선은 -1의 유량이 흘러 유량이 0이 된다.

즉, 유량의 대칭성에 의해 두 유량은 상쇄되었다!

(유량의 상쇄에 대해 잘 모른다면 다음 게시글을 참조하자.)

[네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘

 

결국 남은 간선들에서 +1인 유량을 가지는, 즉 유량이 흐르는 간선들을 조합해보면 다음과 같이 겹치지 않는 올바른 경로가 나온다.

따라서 최대 유량 알고리즘으로 계산 시 겹치지 않는 경로의 개수가 계산되고,

최소 컷에 의해 각각의 경로에서 하나의 간선만 지우면(두 개의 벽만 세우면) K(source)에서 H(sink)로의 모든 경로를 끊을 수 있다.

 

(어렵다 어려워...)

 

코드