def DFS(i):
if visited[i]:
return
visited[i] = 1
for j in graph[i]:
if not match[j]:
match[j] = i
return 1
for j in graph[i]:
if DFS(match[j]):
match[j] = i
return 1
shark = [0]+[[*map(int,input().split())] for i in range(int(input()))]
N = len(shark)
graph = [[] for i in range(N)]
for i in range(1,N):
for j in range(1,N):
i1,i2,i3 = shark[i]; j1,j2,j3 = shark[j]
if i==j or i1<j1 or i2<j2 or i3<j3 or i1==j1 and i2==j2 and i3==j3 and i<j:
continue
graph[i].append(j)
match = [0]*N
for _ in range(2):
for i in range(1,N):
visited = [0]*N
DFS(i)
print(match.count(0)-1)
이분매칭 응용문제
풀이부터 설명하면,
1. a 상어가 b 상어를 먹을 수 있으면, graph[a]에 b를 넣는다. 이때 크기, 속도, 지능이 모두 같아 서로가 서로를 먹을 수 있는 경우에는 인덱스가 작은 상어가 큰 상어를 먹도록 한다.
2. 이분매칭을 두번 실행하여 상어를 먹는다.
3. 매칭되지 못한 상어의 수를 출력한다.
이분매칭 문제라는 사실을 잘 숨겨놓은 문제였다. 언뜻보면 같은 집단 내에서 간선이 있다고 생각하여 이분매칭을 떠올리기 쉽지 않은데, a 상어가 b 상어를 먹을 수 있는 경우 b 상어는 a 상어를 먹을 수 없기에 먹는 과정에서 간섭이 일어나지 않아 똑같은 집단이 두 개가 있다고 생각하고 두 집단 간의 이분매칭을 실행해줄 수 있다. 단, 크기 속도 지능이 모두 같아 서로가 서로를 먹을 수 있는 경우가 존재하는데, 이 경우에만 1번처럼 예외처리를 해주어 해결할 수 있었다.
처음에는 모두 같은 상어는 중복을 제거해서 해결할 수 있다고 생각했는데, 이 경우에는 반례가 존재한다는 것을 알게되었다.
이분매칭 문제라는 사실을 모른채로 풀었으면 더 어려웠을 것 같은 문제였다.
오늘의 교훈) 다양한 이분매칭 문제를 해결하자