[백준]6086 최대유량 #최대유량#에드몬드_카프#파이썬

1. 풀이

최대유량을 구해주기 위해선, 시점부터 종점까지 (1)가능한 경로와 경로상의 최소 유량 찾기, (2)현재상태를 업데이트 하는 과정을 더이상 가능한 경로가 없을 때 까지 해주면 된다. 

각각의 과정에 대한 구체적인 설명은 다음과 같다.

(1) 가능한 경로와 그때의 유량 찾기

- bfs

경로를 찾을 때는 bfs로 탐색을 한다. 이때 한번 탐색한 노드는 다시 탐색하지 않기 위해 (흔히 bfs문제를 풀 때 하는) visited노드로 관리를 해줘야 한다.

이때 단순히 방문하면 1, 그렇지 않으면 0으로 하는게 아니라 해당 노드의 경로상의 직전의 노드를 저장해놓는다 (그래서 이름도 visited가 아니라 prev로 한다). 

왜냐하면 (2)현재상태를 업데이트 에서 경로를 따라가며 상태를 업데이트 해야 하기 때문에다.

 

- 탐색조건

단순 경로찾기 bfs문제를 풀때 조건에는 visited가 0인지, 앞으로 탐색할 위치가 벽으로 가로막혀있는진 않는지, 범위 밖으로 나가진 않는지 등등이였다면, 최대유량 문제에선 현재의 flow가 해당 간선의 최대 flow를 넘지 않았는지 와 (bfs와 마찬가지로)prev가 -1인지 가 조건이 된다.

해당 조건에 맞게 쭉 찾다가 종점이 나오면 그만 찾고 큐에서 나오면 된다.

            if (c[now][next]-flow[now][next])>0 and prev[next]==-1:
                q.append(next)
                prev[next]=now

 

- 최소 유량 찾기

찾은 경로에서 흐를 수 있는 가장 큰 유량은, 경로상에 있는 간선의 용량 중 가장 작은 것이다.

예를들어 경로가 (A-4-B-3-C-2-D)인데 3이 흐르면 C-2-D에서 막히니까, 당연히 최소용량(C-D사이의 용량)인 2가 흘러야 한다

 

 

 

(2) 현재상태 업데이트

경로를 찾았으면, 찾은 경로를 따라 찾은 (최소)유량만큼 업데이트를 쭉쭉 해주면된다.

이렇게 끝나면 어려울게 없는데 여기에서 가장 이해가 안되는 부분이 나온다.

바로 특정 간선의 유량을 업데이트 해줄 때 해당 간선의 반대방향도 -로 업데이트를 해줘야 하는 것이다.

즉 A->B로 3만큼 흐르면, B->A만큼 -3만큼 흐르도록 업데이트를 해줘야 하는 것이다.

그렇게 안해주면 찾는 경로의 순서에 따라 최대로 흐르지 않았는데도 끝나기 때문이다. 이를 그림으로 표현하면 다음과 같다.

 

 

2. 소스코드

from collections import deque

INF=9876543210
maxNum=52


def toNum(alpa):
    if ord(alpa)<=ord('Z'):
        return ord(alpa)-ord('A')
    else:
        return ord(alpa)-ord('a')+26

def findMin(node):
    global minFlow
    if node==0:
        return

    rest=c[prev[node]][node]-flow[prev[node]][node]
    if rest<minFlow:
        minFlow=rest
    findMin(prev[node])

def makeFlow(node):
    if node==0:
        return
    flow[prev[node]][node]+=minFlow
    flow[node][prev[node]]-=minFlow

    makeFlow(prev[node])

N=int(input())
graph={}
c=[[0 for j in range(maxNum)] for i in range(maxNum)]
flow=[[0 for j in range(maxNum)] for i in range(maxNum)]
totalFlow=0
fin=toNum('Z')

for i in range(maxNum):
    graph[i]=[]

for i in range(N):
    a,b,cost=input().split()
    numA=toNum(a)
    numB=toNum(b)
    cost=int(cost)

    c[numA][numB] += cost
    c[numB][numA] += cost
    graph[numA].append(numB)
    graph[numB].append(numA)

while(1):
    prev=[-1 for i in range(maxNum)]
    q=deque([0])

    while(q):
        now=q.popleft()
        if now==fin:
            break

        for next in graph[now]:
            if (c[now][next]-flow[now][next])>0 and prev[next]==-1:
                q.append(next)
                prev[next]=now

    #한번 돌았는데 z까지 못가면?
    if prev[fin]==-1:
        break

    #A에서 Z로 가는 경로 중 가장 작은 용량?
    minFlow=INF
    findMin(fin)
    #경로상의 가장 작은양(min_flow)만큼 물을 흘림, 반대방향으론 -만큼
    makeFlow(fin)

    totalFlow+=minFlow



print(totalFlow)