[BOJ] 백준 6086번 최대 유량 (Java)

#6086 최대 유량

난이도 : 플레 4

유형 : 네트워크 유량 / 포드-폴커슨 알고리즘 / 최대 유량

6086번: 최대 유량

▸ 문제

농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다.

두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한개의 용량 3짜리 파이프가 된다.

  +---5---+---3---+    ->    +---3---+

게다가, 병렬로 연결돼 있는 배수관들은 각 용량의 합만큼의 물을 보낼 수 있다.

    +---5---+
 ---+       +---    ->    +---8---+
    +---3---+

마지막으로, 어떤 것에도 연결돼 있지 않은 파이프는 물을 흐르게 하지 못하므로 제거된다.

    +---5---+
 ---+               ->    +---3---+
    +---3---+--

이로 인해 복잡하게 연결된 모든 배수관들은 한개의 최대 유량을 갖는 배수관으로 만들어진다.

주어진 파이프들의 맵으로부터 우물(A)와 외양간(Z) 사이의 유량을 결정하라.

각 노드의 이름은 알파벳으로 지어져 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +---3---+---5---+---4---+
                         C       D

파이프 BC와 CD는 합쳐질 수 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----3-----+-----4-----+
                             D

그러면 BD와 DZ 역시 합쳐질 수 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----------3-----------+

병렬 연결된 BZ 역시 합쳐진다.

                 B
        A+---3---+---9---+Z

그러면 AB와 BZ 역시 합쳐질 수 있고 용량 3인 배수관 하나가 만들어진다.

        A+---3---+Z

한 파이프들의 집합을 읽고. 두개의 끝점을 가진 파이프로 만들어놓은 뒤 A부터 Z까지 흐르는 최대 유량을 계산하라. 모든 파이프들은 위의 규칙을 적용시켜 줄일 수 있다.

i번째 파이프는 두개의 다른 노드 ai와 bi와 연결돼 있고 Fi (1 ≤ Fi ≤ 1,000)만큼의 유량을 갖는다. 알파벳은 같지만, 대소문자가 다르면 다른 문자이다. 파이프는 양방향으로 흐를 수 있다.

▸ 입력

첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위치에 파이프의 용량이 주어진다.

▸ 출력

첫째 줄에 A에서 Z까지의 최대 유량을 출력한다.

 

문제 풀이  

네트워크 유량 문제로 포드-폴커슨 알고리즘을 사용하여 풀이를 해야 한다. 포드-폴커슨 알고리즘의 동작 원리는 아주 간단하다.

1. 유량 네트워크의 모든 간선의 유량을 0으로 두고 시작해,
2. 소스에서 싱크로 유량을 더 보낼 수 있는 경로를 찾아 유량을 보내기를 반복한다.

 

s에서 t로 최대 유량 찾기

 

포드-폴커슨 알고리즘의 자세한 내용은 여기를 참고해주세요.

 

시뮬레이션

흐름을 더 잘 이해하기 위해 주어진 예제와는 값이 좀 다르게 변형해서 시뮬레이션을 돌려보자. 유량의 초기 상태는 다음과 같다.

초기 상태

 

1. src = A를 시작으로 잔여 용량이 남아있는 간선을 BFS를 통해 탐색한다.

• A-B 잔여용량 = 6-0 = 6
• B-Z 잔여용량 = 3-0 = 3
• B-C 잔여용량 = 3-0 = 3
• Z에 도달한 간선이 있으므로 BFS 탐색 종료

 

src=0으로 시작한 첫 BFS 탐색

 

2. 1번에서 탐색한 정보를 통해 증가 경로를 통해 유량을 얼마나 보낼지 결정한 후 유량을 내보낸다.

• B-Z의 최대 유량은 3, A-B의 최대 유량은 6 이므로 유량은 3이다.
• 구한 유량의 양을 그대로 src(A)에서 sink(Z)로 내보낸다. 단, 여기서 대칭성을 고려하여 반대 유량도 고려해줘야 한다.
  • flow[A][B] = 3, flow[B][A] = -3
  • flow[B][Z] = 3, flow[Z][B] = -3

 

증가 경로를 통해 유량을 흘려보낸다.

 

3. 새롭게 다시 다른 잔여용량이 남아있는지 BFS를 통해 탐색한다.

• A-B 잔여용량 = 6-3 = 3
• B-C 잔여용량 = 3-0 = 3
• C-D 잔여용량 = 5-0 = 5
• D-Z 잔여용량 = 4-0 = 4
• Z에 도달한 간선이 있으므로 BFS 탐색 종료

src=0으로 시작한 두번째 BFS 탐색

 

4. 2번과 마찬가지로 증가 경로를 통해 보낼 유량의 크기를 구하여 보내준다.

• 3번에서 구한 잔여 용량의 최소는 3이므로 최대로 보낼 수 있는 유량은 3이다.
• 구한 유량의 양을 그대로 src(A)에서 sink(Z)로 내보낸다. 단, 여기서 대칭성을 고려하여 반대 유량도 고려해줘야 한다.

최대 유량은 6이다

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	static int INF = 987654321, V = 52;
	static int[][] flow, capacity;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		flow = new int[V][V];
		capacity = new int[V][V];
		StringTokenizer st;
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int a = atoi(st.nextToken().charAt(0));
			int b = atoi(st.nextToken().charAt(0));
			int cost = Integer.parseInt(st.nextToken());
			
			capacity[a][b] += cost;
			capacity[b][a] += cost;
		}
		
		maxFlow(0,25);
	}
	
	static void maxFlow(int src, int sink) {
		int totalFlow = 0;
		int[] parent = new int[V];
		Queue<Integer> q;
		while(true) {
			Arrays.fill(parent, -1);
			q = new LinkedList<>();
			
			parent[src] = src;
			q.add(src);
			
			while(!q.isEmpty() && parent[sink] == -1) {
				int cur = q.poll();
				for(int nxt =0; nxt<V; nxt++) {
					// 잔여 용량이 남아 있는 간선을 따라 탐색한다. 
					if(capacity[cur][nxt] - flow[cur][nxt] > 0 && parent[nxt] == -1) {
						q.add(nxt);
						parent[nxt] = cur;
					}
				}
			}
			
			// 더이상 증가 경로가 없으면 종료 
			if(parent[sink] == -1) break;
			
			// 증가 경로를 통해 유량을 얼마나 보낼지 결정한다. 
			int amount = Integer.MAX_VALUE;
			for(int i=sink; i!=src; i=parent[i]) {
				amount = Math.min(capacity[parent[i]][i] - flow[parent[i]][i], amount);
			}
			
			// 증가 경로를 통해 유량을 보낸다. 
			for(int i=sink; i!=src; i=parent[i]) {
				flow[parent[i]][i] += amount;
				flow[i][parent[i]] -= amount;
			}
			
			totalFlow += amount;
			
		}
		System.out.println(totalFlow);
	}
	
	static int atoi(char c) {
		if('A' <= c && c <= 'Z') {
			return c-'A';
		}else if('a' <= c && c <= 'z'){
			return c-'A'-6;
		}
		return -1;
	}
}