BOJ 1671 상어의 저녁식사

https://www.acmicpc.net/problem/1671
시간 2초, 메모리 128MB

input :

• N (1 ≤ N ≤ 50)
• 각 상어의 크기, 속도, 지능의 정보

output :

• 살아남을 수 있는 상어 수의 최솟값을 출력

조건 :

• 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크거나 같다면 상어 A는 상어 B를 먹을 수 있다

• 한 상어가 최대 두 개의 상어만 먹을 수 있게 했다.

• 상어가 공멸하는 경우가 없다

---

학기 중 시험 문제 풀이를 위해 공부한 이분매칭 문제이다.
다른 부분들 보다 "상어가 공멸하지 않기 위해 나온 아이디어가 제일 중요하다".

주어진 정보들을 이용해서 자신이 먹을 수 있는 상어들을 모두 기록한다. => 식사를 할 때 먹을 수 있는 것들을 확인해야 하기 때문에

동등한 능력치를 가진 상어에 대해서는 1마리만 상대를 먹을 수 있다. => 공멸에 대한 대책.
1마리만 먹도록 가지고 있는 idx를 비교할 수 있다.

이분 매칭을 통해 연결 => 최적의 방법을 구할 수 있다.
dfs의 기저 사례는 이미 방문한 경우이다.
방문한 경우 => 먹을 수 있는 상어를 이미 탐색했다.

그리고 for문을 통해 먹을 수 있는 상어가 아직 있는지, 아니면 그 상어를 포식하려는 상어에게 다른 선택지가 존재하는지 확인한다.

문제에서 문제가 되는 부분은 공멸이었다. 이를 해결할 수 있다면 서로가 서로를 먹는 예외적인 일이 생기지 않아서 문제를 해결할 수 있다.

import sys

def dfs(node):
    if visit[node]:
        return False

    visit[node] = 1

    for next_node in food[node]:
        prev = ans[next_node]
        if prev == -1:
            ans[next_node] = node
            return True

        if dfs(prev):
            ans[next_node] = node
            return True

    return False

n = int(sys.stdin.readline())
graph, ans, food = [], [-1] * n, dict()

for i in range(n):
    size, speed, brain = map(int, sys.stdin.readline().split())
    graph.append((size, speed, brain))
    food[i] = []

for i in range(n):
    for j in range(n):
        if i == j:
            continue

        if graph[i][0] == graph[j][0] and graph[i][1] == graph[j][1] and graph[i][2] == graph[j][2] and i > j:
            continue

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

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

print(ans.count(-1))