백준 2367번: 파티 (Maximum Flow)

문제링크:2367번: 파티 (acmicpc.net)

2367번: 파티

이 문제는 최대 유량을 이용한 문제이다. 최대 유량이란 그래프의 각 간선마다 최대로 흘려보낼 수 있는 가중치가 정해져있을 때, 시작 노드 (source) 에서 끝 노드 (sink) 까지 보낼 수 있는 가중치들의 최대 합을 구하는 문제이다. 최대 유량문제를 해결하는 방법에는 여러가지 알고리즘이 있지만 흔히 사용하는 에드몬드-카프 알고리즘을 사용해서 문제를 해결하였다.

 

각 간선이 보낼 수 있는 가중치를 capability 라고 하고, 각 간선에서 실제로 흐르는 유량을 flow라고 한다. 각 간선에 상황에 맞춰 capability를 인접 행렬 형식으로 저장하고, flow도 인접 행렬 형식으로 저장한다. 아직 흘려보낸 유량이 없다면 flow의 초기값은 당연히 0이 될 것이다.

 

에드몬드 카프 알고리즘은 먼저 source에서 BFS를 해 가며 sink로 갈 수 있는 제일 빠른 경로를 탐색한다. 그리고 그 경로에서 흘려보낼 수 있는 경로의 최대 유량을 흘려보낸다. 경로에서 흘려보낼 수 있는 최대 유량을 amount라고 하면, amount는 당연히 경로의 간선 중 가장 작은 capability 를 가진 간선일 것이다. 다음으로 그 경로 방향을 따라 flow를 amount만큼 더해 주며 업데이트 해 준다. 특이한 점은 여기서 경로의 역방향 (sink에서 source) 까지의 경로에 amount만큼 빼 주어 역방향의 flow도 업데이트 해 준다는 것이다. 나도 처음에 그러는 이유를 잘 몰랐는데, 코드를 보면서 이해할 수 있었다.

 

import sys
from collections import deque

N,K,D = map(int,sys.stdin.readline().rstrip().split())

cap = [[0 for _ in range(N+D+2)] for _ in range(N+D+2)]
flow = [[0 for _ in range(N+D+2)] for _ in range(N+D+2)]

source = 0
sink = N+D+1

foodcap = list(map(int,sys.stdin.readline().rstrip().split()))

for people in range(1,N+1): # source -> people
    cap[source][people] = K
    
for i in range(D): # food -> sink
    cap[N+1+i][sink] = foodcap[i]

for people in range(1,N+1): # people -> food
    inputs = list(map(int,sys.stdin.readline().rstrip().split()))
    for end in inputs[1:]:
        cap[people][N+end] = 1

ans = 0

while 1: #가능한 모든 source->sink 최소 경로 찾기
    que = deque()
    que.append(source)
    parent = [-1 for _ in range(N+D+2)]
    parent[source] = source
    while que:
        cur = que.popleft()
        for end in range(1,N+D+2):
            if cap[cur][end] - flow[cur][end] > 0 and parent[end] == -1:
                que.append(end)
                parent[end] = cur
    
    if parent[sink] == -1: #flow가 cap에 맞게 채워져서 sink로 못갈때
        break
        
    amount = 99999999

    #가능한 flow 양
    rfrom = sink
    while rfrom != source:
        rto = parent[rfrom]
        amount = min(cap[rto][rfrom]-flow[rto][rfrom], amount)
        rfrom = rto

    #flow 양만큼 채워주기
    rfrom = sink
    while rfrom != source:
        rto = parent[rfrom]
        flow[rto][rfrom] += amount
        flow[rfrom][rto] -= amount
        rfrom = rto
        
    ans += amount

print(ans)

문제에서 사람마다 준비할 수 있는 음식은 K로 cap[source][people] = K 로 조정 해 주고, 사람이 준비할 수 있는 음식이 있다면 cap[people][food] = 1 (각 음식 당 하나만 준비 가능) 로 조정 해 준다. 각 음식 당 최대로 가져올 수 있는 음식은 foodcap에 저장하고, cap[food][sink] = foodcap[i] 로 각 음식 당 최대 개수를 저장한다.

 

다음으로 위에서 말한 것처럼 최단 거리 경로를 탐색한다. 최단 거리가 탐색 기준은 그 간선의 최대 용량 - 그 간선에서 흐르고 있는 유량이 0보다 클때, cap[cur][end] - flow[cur][end] > 0 일때, 그리고 최단 거리여야 하므로 해당 end가 방문된 적이 없는 경우에만 탐색한다. parent리스트에 end를 저장해서 start->sink의 경로가 저장될 수 있도록 한다.

 

만약 모든 간선이 유량으로 꽉 차면 sink에 도달하지 못하고 que가 끝나므로 parent[sink] == -1이 될 것이다. 이때는 최대 유량을 모두 구한 경우이므로 탐색을 종료한다.

 

다음으로 amount를 구하기 위해 sink에서 parent[sink]를 따라가며 해당 간선의 여유 용량 (cap[rto][rfrom] - flow[rto][rfrom]) 을 확인 해 가며 start까지 탐색한다. rto -> rfrom인 이유는 rfrom이 sink에서 시작하며 역방향으로 탐색하기 때문이다. 그리고 구한 amount만큼 flow를 채워주며 업데이트 한다.

 

여기서 경로의 역방향 간선들을 -=amount로 업데이트 해주는 이유는 만약 실제로 기존에는 cap[end][start] = 1이지만,  cap[start][end] 간선이 존재하지 않아 cap[start][end] = 0, flow[start][end] = 0이라고 치자. 그런데 만약 최단 거리 탐색 중 end -> start 거리가 경로에 포함 되어 flow[end][start] =1, flow[start][end] = -1로 갱신되었다 유량을 간선의 역방향에 같은 만큼 음수로 더해준 것이기에 문제가 없다. 위 과정이 있으면 cap[start][end] - flow[start][end] 과정에서 cap이 0임에도 불구하고 flow 가 -1 이 되므로 경로에 포함할 수 있게 된다.

 

간선이 없는데 포함하면 안되는 것 아니냐 할수도 있지만 그렇게 통과한 경로의 amount 1만큼 업데이트 해주면, flow[start][end] += 1, flow[end][start] -= 1 해주어 결국 flow[start][end] = 0, flow[end][start] = 0 이 된다. 결국 start와 end사이에 흐르는 유량은 없어 start -> end 간선이 없는 경우와 마찬가지가 되고, 각각 start노드와 end노드에서 뻗어나가는 모든 가능한 간선들의 유량들을 탐색 할 수 있게 되었다.

 

위 과정을 통해 만약 BFS 순서떄문에 만약 end노드에서 두갈래로 갈 수 있는 경로가 있을때, 첫번째 탐색에서 한 경로로 최대 유량을 쏴주어 다른 경로가 남는데도 유량을 쏘지 못하는 경우를 탐색할 수 있게 한다.