[백준 1671번] 상어의 저녁식사 (Python3)

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번처럼 예외처리를 해주어 해결할 수 있었다.

처음에는 모두 같은 상어는 중복을 제거해서 해결할 수 있다고 생각했는데, 이 경우에는 반례가 존재한다는 것을 알게되었다.

이분매칭 문제라는 사실을 모른채로 풀었으면 더 어려웠을 것 같은 문제였다.

 

오늘의 교훈) 다양한 이분매칭 문제를 해결하자