[백준] 17412 도시왕복하기 1 - 네트워크 플로우 알고리즘(에드몬드 카프 알고리즘)

문제

---

N개의 도시가 P개의 단방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 가며 워해머를 한다. 성실한 이석원은 1번에서 2번으로 가는 서로 다른 경로를 최대한 많이 찾으려고 하는데, 이때 한 경로에 포함된 길이 다른 경로에 포함되면 안된다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다. 도시의 번호는 1번부터 N번까지이다.

 

 

 

 

풀이

---

문제가 다소 불친절하게 설명 돼있어서조금 더 부연설명을 하자면,

 

한 경로에 포함된 길이 다른 경로에 포함되면 안된다라는 말은

해당 노드로 들어오는 간선의 수만큼 다른 노드로 갈 수 있다.

이 때 만들 수 있는 경로의 최선의 값을 찾는 것이다.

 

이문제는 네트워크 플로우 알고리즘을 알아야 이해하기 쉽다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ndb796&logNo=221237111220 

27. 네트워크 플로우(Network Flow)

위 블로그는 네트워크 플로우를 이해하기위해 참고한 블로그다.

 

네트워크 플로우 알고리즘을 이용해서 문제를 풀면

여기서 간선은 최대 값이 1로 동일하다.

따라서 capacity 는 1이다.

 

만약 capacity 값보다 flow 값이 작아 지나갈 수 있는 경로면 그때의 출발 노드를 저장해 둔다. (역 추적하면서 flow 값을 조정할 때 사용하기 위해)

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {	
	static int n, p;
	static int[][] capacity; // i -> j 로 가는 간선 용량
	static int[][] flow;     // i -> j 로 현재 흐르고 있는 유량
	static List<Integer>[] map;
	static int[] visited;
	static int answer = 0;
	static StringBuilder sb = new StringBuilder();

	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = parseInt(st.nextToken());
		p = parseInt(st.nextToken());
		
		capacity = new int[n + 1][n + 1];
		flow = new int[n + 1][n + 1];
		visited = new int[n + 1];
		map = new List[n + 1];
		for(int i = 1 ; i <= n ; i++) {
			map[i] = new ArrayList<>();
		}
		
		for(int i = 0 ; i < p ; i++) {
			st = new StringTokenizer(br.readLine());
			
			int u = parseInt(st.nextToken());
			int v = parseInt(st.nextToken());
			
			//단방향이지만 역방향 간선도 저장을 해둔다
			map[u].add(v);
			map[v].add(u);
			
			// 용량은 1
			capacity[u][v] = 1;
		}
		
		answer = 0;
		bfs();		
		
		System.out.println(answer);
	}
	
	static void bfs() {
		
		while(true) {
			
			Queue<Integer> queue = new LinkedList<>();
			Arrays.fill(visited, -1);
			queue.offer(1);
			
			while(!queue.isEmpty()) {
				int cur = queue.poll();
				
				for(int next : map[cur]) {
					if(visited[next] != -1) continue;
					
					//용량보다 flow가 작으면 더 흐르게 할 수 있으므로 queue에 추가한다.
					if(capacity[cur][next] > flow[cur][next]) {
						visited[next] = cur;
						if(next == 2) break;
						
						queue.offer(next);
					}
				}				
			}
			
			//더이상 돌아갈 곳이 없다.
			if(visited[2] == -1) break;
			
			for(int i = 2 ; i != 1 ; i = visited[i]) {
				flow[visited[i]][i] += 1;
				flow[i][visited[i]] -= 1;
			}
			
			answer += 1;
		}
	}
}

 

---

참고

만약 capacity 가 주어지는 문제면 이때의 값을 1이 아닌 더 큰값으로 하면 된다.

for(int i = 2 ; i != 1 ; i = visited[i]) {
	flow[visited[i]][i] += 1;
	flow[i][visited[i]] -= 1;
}

위 행위를 하기 전에 가장 적은 flow 값을 구해줘야 한다.