백준 6086번: 최대 유량 #파이썬

구글에서 해당 문제를 검색해보면 대부분 에드몬드 카프 알고리즘에 대해 설명하고 있습니다. 하지만 에드몬드 카프 알고리즘으로 해당 문제를 풀려고 하면 상당히 혼란스러운데, 사실 에드몬드 카프 알고리즘이 최적해가 아니기 때문입니다. 게다가 파이썬으로 설명한 사람도 매우 적어서 Java나 C++ 코드가 어려운 사람은 도움을 받기 힘들어 보였습니다. 그래서 작성하는 풀이법입니다.

 

아이디어

1. 직렬 연결 시 유량의 최소값만큼 흘려보낼 수 있다.

2. 병렬 연결 시 유량의 합만큼 흘려보낼 수 있다.

A에서 Z에 도달할 수 있는 방법들을 찾고, 각 방법에서 흘려보낼 수 있는 유량을 찾고, 각 유량만큼 계속 더한 값이 정답이다.

 

예제

제공된 예제를 조금만 변경해봅시다. (A B 3 --> A B 5, B Z 6 -> B Z 4)

5
A B 5
B C 3
C D 5
D Z 4
B Z 4

 

먼저 A에서 Z로 이동할 수 있는 경우의 수를 찾아봅시다.

A -> B -> Z가 있군요.

A -> B는 5, B -> Z는 4만큼 흘려보낼 수 있습니다.

따라서 해당 방법에서 흘려보낼 수 있는 유량은 4입니다.

4만큼 흘려보냈다고 가정하면 이제 A -> B는 1만큼 B -> Z는 0만큼 흘려보낼 수 있습니다.

정답 = 4라고 가정하고 데이터를 업데이트 해줍시다.

 

5
A B 1
B C 3
C D 5
D Z 4
B Z 0

A에서 Z로 이동할 수 있는 경우의 수를 또 찾아봅시다.

A -> B -> C -> D -> Z가 있군요.

A -> B는 1, B -> C는 3, C -> D는 5, D -> Z는 4만큼 흘려보낼 수 있습니다.

따라서 해당 방법에서 흘려보낼 수 있는 유량은 1입니다.

1만큼 흘려보냈다고 가정하면 이제 A -> B는 0만큼 B -> C는 2만큼, C -> D는 4만큼, D -> Z는 3만큼 흘려보낼 수 있습니다.

정답 = 4 + 1이라고 가정하고 데이터를 업데이트 해줍시다.

 

5
A B 0
B C 2
C D 4
D Z 3
B Z 0

A에서 Z로 이동할 수 있는 경우의 수를 계속해서 찾아봅시다.

.......

더 이상 찾아볼 수가 없군요.

정답을 출력합니다. 

 

코드

import sys
from collections import deque

# 파이프의 정보 수
n = int(sys.stdin.readline())

# A -> 0, Z -> 51, 나머지 알파벳 -> 1~50
alphabets = ['A'] + [chr(i+ord('a')) for i in range(26)] + [chr(i+ord('B')) for i in range(25)]
alphabets_dict = dict()
for idx, alphabet in enumerate(alphabets):
    alphabets_dict[alphabet] = idx

# 파이프 정보 입력
pipes = [[0] * 52 for _ in range(52)]
for _ in range(n):
    pipe_1, pipe_2, flow = sys.stdin.readline().split()
    pipes[alphabets_dict[pipe_1]][alphabets_dict[pipe_2]] += int(flow)
    pipes[alphabets_dict[pipe_2]][alphabets_dict[pipe_1]] += int(flow)

# 최대 유량 탐색
total_flow = 0
while True:
    q = deque()
    parents = [-1] * 52
    
    q.append(0)
    parents[0] = 0
    
    # 'A'에서 출발하여 'Z'에 도착할 수 있는 방법 탐색 
    while q and parents[51] == -1:
        cur = q.popleft()
        for nxt in range(52):
            if pipes[cur][nxt] > 0 and parents[nxt] == -1:
                q.append(nxt)
                parents[nxt] = cur

    # 더 이상 'Z'에 도착할 수 없다면 종료
    if parents[51] == -1: break

    # 해당 방법으로 흘려보낼 수 있는 유량 탐색
    max_flow = 10 ** 3
    idx = 51
    while idx != 0:
        max_flow = min(max_flow, pipes[parents[idx]][idx])
        idx = parents[idx]

    # 해당 유량은 더 이상 이용 불가
    idx = 51
    while idx != 0:
        pipes[parents[idx]][idx] -= max_flow 
        idx = parents[idx]

    total_flow += max_flow

# 정답 출력
print(total_flow)