[Python 3] BOJ - 1658 "돼지 잡기"

 # 문제 링크 : https://www.acmicpc.net/problem/1658

1658번: 돼지 잡기

 # 풀이 :

 개인적으로 이 문제의 핵심은 최대 유량이라고 생각한다. 그보다도 어떻게 최대 유량을 모델링하는지가 더 핵심이라고 생각한다.

<그림 1. 예시 그래프>

 현재 그림 1과 같은 그래프가 존재한다고 가정하자. 이 때 각 간선은 단방향 간선이고 간선에 쓰여있는 표기 n/m에서 m은 정점 a에서 정점 b로 보낼 수 있는 유량이라고 하고 n은 실제로 정점 a에서 정점 b로 보낸 유량이라고 하자. 정점 a에서 정점 b로 유량을 보내면 정점 a와 b사이의 간선은 다시 갈 수 없다고 가정하고 한번이라도 도착 정점에 유량이 도달한다면 나머지 정점에서 다른 정점으로 갈 수 있다 하더라도 유량을 보내는 작업을 중지하고 더이상 남은 간선이 없을 때 까지 반복한다고 가정할 때 정점 1에서 정점 2로 유량을 보낼 때 2에 도착하는 유량들의 최대값을 얼마일까?

<그림 2. 정점 1에서 정점 2로 유량을 10만큼 보낸 경우>

 그림 2에서는 정점 1에서 정점 4로 유량을 10만큼 보냈다. 따라서 정점 4는 정점 1로부터 10만큼의 유량을 받았다. 그런데 정점 4에서 정점 3으로 유량을 보내려면 2만큼만 보낼 수 있으므로 정점 3으로 2만큼 유량을 보낸다. 따라서 현재 정점 4가 가지고 있는 유량은 8이다. 또한 정점 4에서 정점 2로 유량을 보내려면 역시 5만큼만 보낼 수 있으므로 정점 2로 5만큼 유량을 보낸다. 따라서 정점 4가 가진 유량은 3이고 정점 3이 가진 유량은 2이다. 결과적으로 도착하고자 하는 정점 2에 5만큼의 유량이 도착했다.

<그림 3. 모든 간선을 이동한 경우>

 그림 2에서 정점 4는 3만큼, 정점 3은 2만큼의 유량을 가지고 있다. 그런데 가정에 따라 그림 2의 경로의 간선들을 갈 수 없다. 따라서 정점 1에서 정점 3에 7만큼의 유량을 보낸다. 따라서 정점 3에서는 이전에 가지고 있던 2만큼의 유량에 현재 정점 1에서 보낸 7만큼의 유량을 합해 총 9만큼의 유량을 가지게 된다. 정점 3에서 도착 정점인 정점 2로 3만큼의 유량을 보내면 도착 정점 2는 8만큼의 유량을 가지게 된다. 따라서 정점 1에서 정점 2로 유량을 보낼 때 정점 2가 가질 수 있는 최대유량은 8이다.

 그런데 그림2와 그림3에서 보았듯, 아무리 정점 i가 유량을 많이 가지고 있다 하더라도 정점 j로 가는 간선으로 보낼 수 있는 유량보다 많다면, 간선으로 보낼 수 있는 유량만큼 보낼 수 밖에 없다. 그런데 정점 i가 간선이 허락하는 유량보다 적다면 정점 i가 가진 모든 유량을 보내도 문제가 되지 않는다고 생각할 수 있지만 이는 옳지 않다. 유량을 보내는 것만이 목적이 아니라 우리는 '최대' 유량을 구해야 하므로 최소한 가지고 있는 유량과 간선이 허용하는 용량만큼은 같아야 최대유량을 구할 수 있기 때문이다. 그림 3에서 만일 정점 3에서 정점 2로 2만큼의 유량을 보낸다면 최대용량인 3보다 적게 보내게 된것이고 이는 정답인 8보다 작은 7이므로 최대유량이 아니다. 따라서 정점 i에서 정점 j로 갈 때 이것을 반드시 고려해야 한다.

<그림 4. 테스트케이스 모델링>

 그림 4는 문제의 예시 입력 그래프를 나타낸 것이다. 현재 빨간색 점선에 속한 정점 1,2,3이 손님이고 파란색 점선에 속한 정점 4,5,6이 축사라고 하자. 손님이 축사의 돼지를 사므로 손님에서 축사 방향으로 단방향 그래프가 성립한다. 최대유량을 사용하기 위해 시작 정점을 0이라고 하고 끝 정점을 7이라 하자. 그렇다면 위와 같은 모양의 그래프를 그릴 수 있다. 그런데 문제는 손님이 원하는 돼지의 수는 정해져 있지만 손님이 살 수 있는 돼지의 수는 정해지지 않았다는 것이다.

 만일 손님이 축사의 돼지보다 많이 사고자 하는 경우 축사의 돼지보다 많이 살 수는 없으므로 최대 축사에 있는 돼지만큼만 살 수 있으며 반대로 축사의 돼지보다 적게 사고자 하는 경우는 최대 손님이 원하는 만큼 살 수 있다. 따라서 손님정점에서 축사 정점으로 가는 간선의 용량은 무한대가 되어야 하므로 ?에 들어갈 수는 무한대(9,876,543,210)이다.

 그런데 위 그래프로 최대유량을 구하면 문제의 조건 중 팔고 남은 돼지들을 현재 열린 축사를 상대로 재분배할 수 있다는 조건을 만족하지 못한다. 그런데 항상 손님이 들어오는 순서대로 돼지가 구매된다. 따라서 만일 손님 1이 축사 3을 열었다면 손님 3은 축사 3의 열쇠를 가지고 있다고 해도 이미 열려있기 때문에 열쇠의 의미가 없어진다.

<그림 5. 올바른 모델링>

 따라서 열쇠를 공유한다면 굳이 자신이 차례일 때 구매하는 것이 아니라, 열쇠를 공유하는 손님 중 가장 빨리 구매할 수 있는 손님에게 자신이 살 돼지의 수를 알려주고 공유하는 손님 중 가장 빨리 구매할 수 있는 손님이 그런 손님들이 살 돼지의 수를 모두 합해서 사게되면 재분배의 조건을 만족할 수 있다. 왜냐하면 문제에서 손님이 필요한 돼지 수만 입력으로 주어지지, 어느 축사의 돼지를 몇마리 사야 하는지는 입력으로 주어지지 않았지만 각 손님들은 살 수 있는 축사의 경우가 정해져 있기 때문이고 또한 한 사람이 산 축사는 다른 사람이 접근할 수 없다는 조건도 없기 때문이다. 따라서 재분배를 축사입장에서 할 필요가 없이 손님입장에서 해주면 올바른 그래프의 모델링이다.

 추가적으로 손님과 손님간의 단방향 간선의 용량이 무한대인 이유는 손님이 축사로부터 사기 원하는 희망 구매 수는 무한대이기 때문이다. 만일 무한대 보다 작다면 앞서 본 그림 3에서의 경우처럼 최대유량의 경우가 아니기 때문이다. 따라서 문제의 그래프를 먼저 구현하고 공유하는 열쇠를 기준으로 손님들 간의 단방향 간선을 새로 이어주면 정답을 구할 수 있다.

 

# 코드

import sys, collections

# 입력부
n, m = map(int, sys.stdin.readline().split())

# capacity : i에서 j로 갈 때 용량을 저장하는 2차원 배열
capacity = [[0] * 1500 for _ in range(1500)]

# flow : i에서 j로 보낼 수 있는 유량을 저장하는 2차원 배열
flow = [[0] * 1500 for _ in range(1500)]

# adj : i에서 j로 갈 수 있으면 1, 없으면 0인 인접 행렬
adj = [[0] * 1500 for _ in range(1500)]

# pigs : 각 축사에 있는 돼지의 수
pigs = [0] + list(map(int, sys.stdin.readline().split()))

# keys : i번째 열쇠를 가진 가장 빠른 손님의 번호를 저장하는 배열
keys = [-1] * 1500

for i in range(m):
    customer_info = list(map(int, sys.stdin.readline().split()))
    num_of_keys = customer_info[0]
    # 시작 정점인 0번 정점에서 i+1번째 손님 정점을 손님이 구매하고자 하는 돼지의 수를 용량으로 하는 단방향 간선으로 연결한다
    capacity[0][i + 1] = customer_info[-1]
    
    # 인접 행렬 갱신
    adj[0][i + 1] = 1
    adj[i + 1][0] = 1
    
    for j in range(1, len(customer_info) - 1):
        now_key = customer_info[j]
        # 공유 열쇠에 대한 가장 빠른 손님 번호 갱신
        if keys[now_key] == -1:
            keys[now_key] = i + 1
        else:
            if keys[now_key] > i + 1:
                keys[now_key] = i + 1
            # 자신이 공유 열쇠를 가진 사람 중 가장 빠른 번호가 아니라면
            elif keys[now_key] != i + 1:
            
                 # 가장 빠른 손님 쪽으로 무한대 용량의 단방향 간선을 이어준다
                capacity[i + 1][keys[now_key]] = 9876543210
                
                # 인접 행렬 갱신
                adj[i + 1][keys[now_key]] = 1
                adj[keys[now_key]][i + 1] = 1
        
        # 손님에서 축사 쪽으로 단방향 용량 간선을 이어준다
        capacity[i + 1][m + now_key] = 9876543210
        
        # 인접 행렬 갱신
        adj[i + 1][m + now_key] = 1
        adj[m + now_key][i + 1] = 1
        
for i in range(n):
    # 가능한 축사의 수가 1500개 이므로 마지막 인덱스인 1499를 도착 정점으로 한다
    # 이후 각 축사에서 도착 정점 1499를 각 축사의 돼지 수만큼을 용량으로 하는 단방향 간선으로 이어준다
    capacity[m + i + 1][1499] = pigs[i + 1]
    
    # 인접 행렬 갱신
    adj[m + i + 1][1499] = 1
    adj[1499][m + i + 1] = 1

# edmond_karp : 시작정점 s에서 도착정점 t로 갈 때 최대용량을 리턴하는 함수
def edmond_karp(s, t):
    tot_flow = 0
    while True:
        # past : 현재 정점으로 오기 위해 어떤 이전 정점을 거쳐왔는지 저장하는 배열
        past = [-1] * 1500
        q = collections.deque()
        
        # 시작정점 큐에 삽입
        q.append(s)
        
        # BFS 시작
        while q and past[t] == -1:
            cur = q.popleft()
            for i in range(len(adj[cur])):
                next = i
                
                # 인접행렬 상 경로가 없으면 갈 수 없으므로
                if adj[cur][next] != 1:
                    continue
                    
                # 이미 한번 지난 간선은 다시 갈 수 없으므로
                if past[next] != -1:
                    continue
                    
                # 용량보다 적게 유량을 흘리면 최대 유량이 아니므로
                if capacity[cur][next] - flow[cur][next] <= 0:
                    continue
                past[next] = cur
                q.append(next)
                
                # 도착 정점에 유량이 도착한다면 한 경로가 끝나기 때문에 내부 while 탈출
                if next == t:
                    break
                    
        # BFS 실행 후에도 도착점에 도착할 수 없으면 외부 while 탈출
        if past[t] == -1:
            break
            
        # temp_flow : 시작 정점 s에서 도착 정점 t로 가는 경로 중 현재 경로일 떄 도착하는 유량
        temp_flow = 9876543210
        x = t
        while x != s:
            temp_flow = min(temp_flow, (capacity[past[x]][x] - flow[past[x]][x]))
            x = past[x]
        x = t
        
        # past[x]에서 x로 유량을 흘렸으므로 x는 temp_flow만큼 유량을 가지고
        # past[x]에서 x로 유량을 흘렸으므로 past[x]는 temp_flow만큼 유량을 잃는다
        while x != s:
            flow[past[x]][x] += temp_flow
            flow[x][past[x]] -= temp_flow
            x = past[x]
            
        # 한 경로에 대한 유량을 더해주면서 최대 유량 갱신
        tot_flow += temp_flow
    return tot_flow

# 정답 출력
print(edmond_karp(0, 1499))