BOJ 백준 6086 최대 유량 [JAVA]

문제 : https://www.acmicpc.net/problem/6086

 

 

[ 문제 요약 ]

• 다양한 크기의 N 개의 파이프들이 랜덤으로 연결돼있습니다.
• 파이프를 통과하는 유량을 계산해야 합니다. 두 개의 배수관이 한 줄로 연결돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 됩니다.
• 예를 들어 용량이 5인 파이프가 3인 파이프와 연결되면 3짜리 파이프가 되는 것입니다.
• 게다가 병렬로 연결돼 있으면 각 용량의 합만큼 물을 보낼 수 있습니다.

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

• 마지막으로 어떤 것에도 연결돼 있지 않으면 물이 못 흘러 제거됩니다.

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

• 이렇게 하다 보면 한 개의 최대 유량을 갖는 배수관으로 만들어집니다.
• 우물(A)와 외양간(Z) 사이의 유량을 파이프 맵으로부터 도출해 냅니다.
• 각 노드의 이름은 알파벳 대소문자로 되어있습니다.
• 파이프는 중복될 수 있습니다.

 

[ 테스트 케이스 설명 ]

5 // 파이프 개수1<=700
A B 3// 연결 노드 2개와 유량(1<=1000)이 주어집니다. 
B C 3// 대소문자가 다르면 다른 파이프 입니다.
C D 5
D Z 4
B Z 6
A-Z까지 최대 유량 : 3

 

[ 알고리즘 분류 ]

• 구현
• 그래프이론
• 시뮬레이션
• 최대 유량

 

[ 문제 해설 ]

 

이 문제는 알고리즘을 알아야 풀 수 있는 것 같습니다.

	b(2)	
a(5)		d(5)
	c(3)

 

위와 같이 파이프가 되어 있을 때 최대 용량을 구하는 알고리즘을 설명하면 아래와 같습니다.

먼저 조건은, 시작을 a, 도착을 d로 가정합니다. 또한 a, d의 용량은 5, b는 2, c는 3입니다.

문제 조건에 따라 바로 답을 구해보면 b와 c는 병렬이므로 합쳐져서 5가 됩니다. 그 후 모든 용량이 5이므로 정답은 5가 됩니다.

이를 알고리즘으로 풀어쓰면 다음과 같습니다.

1. a에서 d로 가는 직선 경로를 구합니다. (경로를 배열에 마킹해 놓음)
2. 구한 경로를 통해 역으로 d에서 a로 이동하며 경로 사이에 최소 용량을 구합니다. a - b - d로 가는 경로를 먼저 탐색했다고 할 때, 이 경로 사이의 최소 용량은 b(2)가 됩니다.
3. 이 최소 용량을 해당 경로에서 모두에서 빼줍니다. 그럼 아래와 같이 변하게 됩니다. 이때, 뺀 최소 용량을 결과에 더해 줍니다. 이 결과는 추후 정답이 됩니다.
4. 위 과정을 1번 부터 반복합니다.

3. 연산 실행 후 결과


	b(0)	
a(3)		d(3)
	c(3)

 

위 논리 그대로 코드로 구현하면 됩니다.

 

이 알고리즘이 에드몬즈–카프 알고리즘입니다. (위와 같은 방식을 구현하기 위해 BFS로 구현하면 시작에서 종료까지 가장 짧은 경로를 구할 수 있게 됩니다.)

 

추가로 위 설명에서 생략한 부분이 있는데, 경로 되돌림을 고려해야 합니다.( 이 문제는 이 부분을 고려하지 않아도 정답임, 테스트 케이스가 약함 )

위와 같이 랜덤으로 지속적으로 차감하다 보면 잘못된 경로 즉, 최선의 선택이 아닌 경로를 선택할 수 있는데, 이를 되돌릴 수 있도록 역방향에는 차감한 값을 더해주는 것입니다. 이렇게 더해주기만 하면 알고리즘 작동 방식에 의해 모든 경우의 수를 탐색해 최적해를 구합니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
class Main{
	
	static final int MAX = 52;
	static final int start = atoi('A');
	static final int end = atoi('Z');
	static int [][] pipe = new int[MAX + 1][MAX + 1];// 각
	static int []prev = new int[MAX + 1];// A->Z 경로 탐색 중 이전 노드를 담을 배열
	static int N;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		while(N-->0)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = atoi(st.nextToken().charAt(0));
			int b = atoi(st.nextToken().charAt(0));
			int u = Integer.parseInt(st.nextToken());
			// “무방향 파이프”를 양방향 잔여용량으로 초기화, 중복 간선은 합쳐짐
			pipe[a][b] += u;
			pipe[b][a] += u;
		}
		
		int res = 0;
		
		while(true)
		{
			// 이전 노드 위치를 담을 배열 초기화
			Arrays.fill(prev, -1);
			// A->Z 까지의 경로를 prev 배열에 마킹
			bfs();
			// 종료 지점에 더이상 못 가면 종료
			if(prev[end] < 0)
				break;
			// 최소 유량 확인 및 결과 갱신
			res += flow();
		}
		
		System.out.print(res);
	}
	static int flow() {
		int now = end;
		int water = Integer.MAX_VALUE;// 최소 유량
		
		while(now != start)
		{
			// end -> start로 가면서(역방향) 정방향 방향(pipe[prev[now]][now])에 있는 가장 최소 유량을 구함
			water = Math.min(water, pipe[prev[now]][now]);
			now = prev[now];
		}
		
		now = end;
		
		while(now != start)
		{
			// 최소 유량(water)을 정방향에는 마이너스 처리
			pipe[prev[now]][now] -= water;
			// 역방향에는 최소 유량(water)를 플러스 해줌으로 추후 되돌림을 할 수 있게 한다.
			pipe[now][prev[now]] += water;
			now = prev[now];
		}
		
		return water;
	}
	static void bfs() {
		Queue<Integer> q = new ArrayDeque<>();
		prev[start] = start;
		q.add(start);
		
		while(!q.isEmpty())
		{
			int now = q.poll();
			if(now == end)
				return;
			// 인접 노드 모두 탐색
			for(int next = 1; next <= MAX; next++)
			{
				// 잔여 유량이 있고, 방문한적이 없다면 탐색
				if(pipe[now][next] > 0 && prev[next] < 0)
				{
					prev[next] = now;// 이전노드마킹
					q.add(next);
				}
			}
		}
	}
	static int atoi(char c){
		int res = c <= 'Z' ? c - 'A' : c - 'a' + 26;
		return res + 1;
	}
}

 

[ 테스트 케이스 ]

4
A Z 1
A Z 2
A Z 3
A Z 4
답 : 10

3
A E 100
E Z 5
Z E 1
답 : 6

3
A E 100
E Z 1
Z E 5
답 : 6

3
A E 100
Z E 1
E Z 5
답 : 6

3
A E 100
Z E 5
E Z 1
답 : 6

7
A B 3
A D 5
D C 5
B C 1
B E 5
C Z 3
E Z 5
답 : 7

9
A B 3
B C 3
C D 3
A E 3
E D 1
E F 3
F G 3
G Z 3
D Z 3
답 : 6

5
B A 3
C B 3
D C 5
Z D 4
Z B 6
답 : 3