들쥐의 탈출
N(1 ≤ N ≤ 100)마리의 들쥐들과 M(1 ≤ M ≤ 100)개의 땅굴이 있다. 각각의 들쥐는 2차원 평면상의 한 위치에 있고, 각각의 땅굴들도 2차원 평면상의 한 점에 위치한다.
들쥐들을 잡아먹는 매가 들쥐들을 습격했을 때, 쥐들은 매를 피하기 위해서 땅굴 속으로 숨을 수 있다. 모든 쥐들이 땅굴에 숨을 수 있다면 매에 잡아먹히는 쥐가 한 마리도 없겠지만, 각각의 땅굴에는 한 마리의 쥐만 들어갈 수 있을뿐더러 매가 도착하는 시간과 쥐들이 땅굴로 도망치는 속도가 있기 때문에 항상 모든 쥐들이 도망갈 수 있는 것은 아니다.
매는 현재를 기준으로 S(1 ≤ S ≤ 100)초가 지난 후에 지상에 도착한다. 각각의 들쥐들은 매 초당 V(1 ≤ V ≤ 100)만큼의 거리를 움직인다(즉 V가 쥐들의 초속이다). 만약 S초가 되기 전에 들쥐가 땅굴에 도착하게 되면 그 들쥐는 땅굴로 숨을 수 있다. 단, 들쥐가 도착하는 시간이 정확히 S인 경우에도 그 들쥐는 도망칠 수 있는 것으로 간주한다.
들쥐들은 종족 전체의 번영을 위해, 매에 잡아먹히게 되는 들쥐의 수가 최소가 되도록 도망치기로 하였다. 들쥐와 땅굴의 위치, 그리고 들쥐의 속도와 매가 도착하는 시간이 주어졌을 때, 잡아먹히게 되는 들쥐의 최소수를 구하는 프로그램을 작성하시오.
코드
# 이분매칭 알고리즘
# 각 들쥐가 들어갈 수 있는 땅굴 간선 정보
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m, s, v = map(int, input().split())
mouse_list = [0]
holes = [0]
for _ in range(n):
x, y = map(float, input().split())
mouse_list.append((x, y))
for _ in range(m):
x, y = map(float, input().split())
holes.append((x, y))
matched_X = [0] * (n+1)
matched_Y = [0] * (m+1)
def dfs(x):
visited[x] = True
for y in graph[x]:
# y 노드와 매칭된 노드가 없는 경우, x 노드와 매칭
if matched_Y[y] == 0:
matched_Y[y] = x
matched_X[x] = y
return True
# y 노드가 이미 매칭이 되어있는 경우, y 노드와 매칭되어 있는 노드가 다른 노드와 매칭이 가능한지 확인
elif not visited[matched_Y[y]] and dfs(matched_Y[y]):
# 다른 노드와 매칭이 가능한 경우, y 노드와 x 노드를 매칭
matched_Y[y] = x
matched_X[x] = y
return True
return False
# O(N+M)
graph = [[] for _ in range(n+1)] # 각 쥐가 숨을 수 있는 구멍 정보
def is_promising():
for i in range(1, n+1):
x = mouse_list[i][0]
y = mouse_list[i][1]
for j in range(1, m+1):
nx = holes[j][0]
ny = holes[j][1]
if ((x - nx)**2 + (y - ny)**2)**0.5 <= s*v:
graph[i].append(j)
is_promising()
cnt = 0
for i in range(1, n+1):
if not matched_X[i]:
visited = [0] * (n+1)
if dfs(i):
cnt += 1
print(n-cnt)이전에 작성했던 이분매칭 알고리즘을 조금 수정만 하여 해결할 수 있는 문제였다. 이분그래프는 들쥐 그룹과 땅굴 그룹으로 구분하여 각 들쥐가 시간 안에 갈 수 있는 땅굴들을 그래프에 저장해두었다.
그리고 이분매칭 알고리즘을 활용하여 최대 매칭 수를 구한 뒤 전체 들쥐 수에서 빼주었다. (잡아먹히는 들쥐 수를 구해야 하는데 살아남은 들쥐 수를 구해서 몇 번 틀렸다... 문제를 잘 읽자)
