[BOJ 13876] Kill the Werewolf

문제

---

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

풀이

---

각 사람 별로 늑대 인간이라고 드러냈을 때 이길 수 있는지 판단해야 한다.

나머지 N - 1명의 사람들 중, 그들이 투표한 두 명 중에 늑대 인간이 있다면 무조건 늑대 인간을 뽑을 것이다.

늑대 인간을 뽑지 않은 사람들은 투표를 잘 분배해서, 가장 많은 투표 받은 사람의 투표수가 늑대 인간보다 작아야 한다.

늑대 인간도 투표권이 있으므로 늑대 인간이 뽑을 수 있는 대상은 늑대 인간보다 적어도 2표 이상 차이나야 한다.

투표를 한다는 것은 capacity 1짜리 flow network로 생각할 수 있다.

투표수의 제한은, sink로 가는 엣지의 capacity로 조절해 줄 수 있다.

예로 들어, 3번 사람이 5표 이하로 받아야 된다면 (그래야 늑대 인간이 패배한다면) 3번 사람의 노드에서 sink로 가는 엣지의 capacity를 5로 놓으면 된다.

이런 식으로 flow network를 구성한 후, 최종 flow의 크기가 source에서 시작하는 엣지들의 flow의 총합과 같다면, 투표를 잘 분배한 것이므로 늑대 인간이 패배한다.

코드

---

import sys
from collections import deque

n = int(sys.stdin.readline())
vote = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]

ans = 0
for i in range(n):
    graph = [[0] * (2 * n + 2) for _ in range(2 * n + 2)]

    k = 0
    for j in range(n):
        if j != i:
            if (i + 1) in vote[j]:
                k += 1
            else:
                graph[0][j + 1] = 1
                graph[j + 1][vote[j][0] + n] = 1
                graph[j + 1][vote[j][1] + n] = 1
    
    if k > n / 2:
        continue

    if k <= 1:
        ans += 1
        continue

    for j in range(n + 1, 2 * n + 1):
        graph[j][2 * n + 1] = k - 1
    
    graph[vote[i][0] + n][2 * n + 1] -= 1
    graph[vote[i][1] + n][2 * n + 1] -= 1

    total = 0
    while True:
        prev = [-1] * (2 * n + 2)
        queue = deque([0])
        while queue:
            cur = queue.pop()
            for nxt in range(1, 2 * n + 2):
                if (nxt == 2 * n + 1) and graph[cur][-1]:
                    prev[-1] = cur
                    break

                if (prev[nxt] == -1) and graph[cur][nxt]:
                    prev[nxt] = cur
                    queue.append(nxt)

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

        total += 1
        while True:
            cur = prev[nxt]
            graph[cur][nxt] -= 1
            graph[nxt][cur] = 1
            nxt = cur
            if nxt == 0:
                break

    if total < n - k - 1:
        ans += 1

print(ans)