[백준] No.2316 - 도시 왕복하기 2 (C++, 최대 유량, 정점 분할)

문제

 

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

2316번: 도시 왕복하기 2

 

풀이

 

solved.ac 난이도: Platium 3

 

정점 분할 테크닉을 통해 풀어야 하는 최대 유량 문제.

최대 유량에 대해서 잘 모른다면 다음 게시글을 참조하자.

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

 

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

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

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

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

 

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

 

기존의 그래프

 

 

 

in과 out으로 정점 분할

 

 

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

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

 

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

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

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

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

 

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

 

 

 

 

 

하지만 다음과 같은 단순한 구현으로는 왜 문제를 해결할 수 없을까?

모든 그래프 간선의 용량을 1로 설정하고, 방문한 정점은 다시 방문하면 안 되므로 방문 여부를 저장한다.

이제 1번 도시(source)에서 2번 도시(sink)로의 최대 유량을 구하면 경로의 개수를 구할 수 있지 않을까?

 

다음과 같은 그래프를 생각해보자.

첫 번째 증가 경로가 1->3->6->2로 정해졌다면 3과 6번은 더 이상 방문할 수 없다.

이런 경우 1번에서 2번으로의 경로를 더 이상 찾을 수 없다.

 

하지만 문제의 정답은 다음과 같은 두 가지 경로이다.

 

이러한 문제는 정점 분할 시 유량의 대칭성에 의해 해결된다.

위의 그래프를 정점 분할하여 첫 번째 증가 경로에 1의 유량을 흘려준 상태는 다음과 같다.

 

3번의 out 정점에서 6번의 in 정점으로 간선에 +1만큼의 유량이 흘렀으므로 유량의 대칭성에 의해 역방향인 유령 간선

6번의 in 정점에서 3번의 out 정점으로의 간선에는 -1만큼의 유량이 흐른다.

따라서 6번의 in 정점에서 3번의 out 정점으로의 간선의 잔여 용량(= 용량 - 유량)은 +1(=0 -(-1))이 된다.

즉, 해당 간선은 1만큼의 유량을 흘려보내줄 수 있다.

 

여기서 다시 source에서 sink로의 증가 경로를 찾으면 6번의 in 정점에서 3번의 out 정점으로의 간선 이 이용되어 다음과 같은 경로를 찾게 된다.

(새로운 증가 경로는 녹색으로 표시하였다.)

 

 

이제 다시 6번의 in 정점에서 3번의 out 정점으로의 간선을 확인해보면

+1의 유량이 흘러 잔여 용량은 0이 되었고, 역 방향인 3번의 out 정점에서 6번의 in 정점으로 간선은 -1의 유량이 흘러 유량이 0으로 돌아왔다.

즉, 서로의 유량이 상쇄되어 해당 정점의 사이에는 더 이상 유량이 흐르지 않는다.

따라서 +유량이 흐르는 간선만 연결하면 다음과 같이 두 가지 경로를 확인할 수 있다.

 

 

이러한 경로로 증가 경로를 찾은 것과 동일하다.

 

따라서 정점 분할을 통해 구현해야 올바른 정답을 구할 수 있다.

비슷한 문제로 다음 문제도 풀어보자.

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

 

코드