[BOJ 1671] 상어의 저녁식사

문제

---

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

풀이

---

왼쪽에 잡아먹는 입장의 1~N번 노드, 오른쪽에 잡아먹히는 입장의 1~N번 노드를 놓는다.

그리고 잡아먹고 먹히는 관계의 상어들을 엣지로 이어 이분 그래프를 만들어 준다.

그 후 각 왼쪽 노드마다 2번씩 dfs를 돌리며 최대 매칭을 구해준다.

N에서 최대 매칭 수를 빼면 살아남을 수 있는 상어 수의 최솟값이 된다.

주의해야 할 점은, 세 능력치가 완전히 같은 상어들이 존재할 수 있다.

이 경우 엣지를 두 개 모두 이을 시 서로가 서로를 잡아먹는 결과를 초래할 수 있다.

그러므로 입력 순서가 작은 것에서 큰 것으로 한 엣지만 만들어줘야 한다.

코드

---

import sys


def dfs(cur):
    visit[cur] = 1
    for nxt in graph[cur]:
        if (b[nxt] == -1) or (not visit[b[nxt]] and dfs(b[nxt])):
            b[nxt] = cur
            return 1
    return 0


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

for i in range(n):
    for j in range(n):
        if i != j:
            if shark[i] == shark[j]:
                graph[min(i, j)].append(max(i, j))

            elif (shark[i][0] >= shark[j][0]) and (shark[i][1] >= shark[j][1]) and (shark[i][2] >= shark[j][2]):
                graph[i].append(j)

b = [-1] * n
ans = 0

for i in range(2 * n):
    visit = [0] * n
    ans += dfs(i // 2)

print(n - ans)