[백준 2191번] 들쥐의 탈출 (Python3)

def DFS(i):
  if visited[i]:
    return
  visited[i] = 1
  for j in graph[i]:
    if match[j]<0:
      match[j] = i
      return 1
  for j in graph[i]:
    if DFS(match[j]):
      match[j] = i
      return 1

N,M,S,V = map(int,input().split())
rat,hole = [[[*map(float,input().split())] for _ in range(x)] for x in [N,M]]
graph = [[] for i in range(N)]
for i in range(N):
  for j in range(M):
    if (rat[i][0]-hole[j][0])**2+(rat[i][1]-hole[j][1])**2<=(S*V)**2:
      graph[i].append(j)
match = [-1]*M
for i in range(N):
  visited = [0]*N
  DFS(i)
print(N-M+match.count(-1))

간단한 이분매칭 응용문제

 

풀이를 설명하면,

1. 들쥐의 각 위치에 따라 시간내에 이동할 수 있는 구멍을 간선으로 저장한다.

2. 이분매칭으로 매칭수를 구한다.

3. N-매칭수를 출력한다. (M-매칭수를 출력하지 않도록 주의)

 

그래프를 만드는 방식만 제외하면 이분매칭 기본문제와 크게 다르지 않다.

 

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