[BOJ 1658] 돼지 잡기

문제

---

https://www.acmicpc.net/problem/1658

풀이

---

그래프를 구상하기 난감한 문제였다.

(i번째 손님, j번째 돼지우리)를 하나의 노드로 만들어 n * m개의 노드를 먼저 만들어 준다.

source와 첫 번째 손님의 노드들을 이어주는데, 이때 capacity는 초기 돼지 숫자이다.

‘i번째 손님에게 팔리는 돼지’ 노드를 만들어, 그날 열리는 돼지 우리와 연결시켜준다.

이때 capacity는 무한대이다.

‘i번째 손님에게 팔리는 돼지’ 노드들은 sink와 연결시켜주는데, capacity는 i번째 손님이 구매하고자 하는 최대 돼지 수이다.

(i번째 손님, j번째 돼지우리) 노드에서 ((i + 1)번째 손님, j번째 돼지우리) 노드로 무한대 capacity 엣지를 잇는다.

i번째 손님이 가지고 있는 열쇠들에 대해, 각 열쇠에 해당하는 우리 속 돼지들은 섞을 수 있으므로, (i + 1)번째 손님의 노드들과 무한대 capacity 엣지로 모두 이어준다.

예로 들어 3번 손님이 1번, 2번 열쇠를 가지고 있다면, (3, 1) -> (4, 2), (3, 2) -> (4, 1) 엣지를 잇는 것이다.

물론 마지막 손님에 대해서는 예외이다.

코드

---

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
k = n * m + m + 2

pig = list(map(int, sys.stdin.readline().split()))
graph = [[] for _ in range(k)]

for i in range(n):
    graph[k - 2].append([i, pig[i]])

for j in range(m):
    num = list(map(int, sys.stdin.readline().split()))
    a = num[0]
    graph[n * m + j].append([k - 1, num[-1]])

    for i in range(1, a + 1):
        graph[n * j + num[i] - 1].append([n * m + j, float('inf')])

    if j != m - 1:
        for i in range(n):
            graph[n * j + i].append([n * (j + 1) + i, float('inf')])
        
        for x in range(1, a + 1):
            for y in range(x + 1, a + 1):
                graph[n * j + num[x] - 1].append([n * (j + 1) + num[y] - 1, float('inf')])
                graph[n * j + num[y] - 1].append([n * (j + 1) + num[x] - 1, float('inf')])

ans = 0
while True:
    prev = [-1] * k
    queue = deque([(k - 2, float('inf'))])
    while queue:
        cur, res = queue.popleft()

        for nxt, capacity in graph[cur]:
            if (nxt == k - 1) and capacity:
                res = min(res, capacity)
                prev[-1] = cur
                break
            
            if (prev[nxt] == -1) and capacity:
                prev[nxt] = cur
                queue.append((nxt, min(res, capacity)))

        if prev[-1] != -1:
            break
    
    if prev[-1] == -1:
        break

    ans += res
    while True:
        cur = prev[nxt]
        for z in range(len(graph[cur])):
            if graph[cur][z][0] == nxt:
                graph[cur][z][1] -= res
                break
        
        for z in range(len(graph[nxt])):
            if graph[nxt][z][0] == cur:
                graph[nxt][z][1] += res
                break
        else:
            graph[nxt].append([cur, res])
        
        nxt = cur
        if nxt == k - 2:
            break

print(ans)

graph를 지금까지처럼 인접 행렬로 구현하면 파이썬 계열은 바로 MLE를 받는다.

그래서 graph를 인접 리스트로 구현해야 한다.