들쥐의 탈출

#BOJ2191

우선 어제 아기상어 그놈한테 뒤지게 당해서 죽는 줄 알았다. 사실 어제도 쓸까 했는데 퇴근 할 때까지 아기상어랑 싸우고 있었다. 풀이 자체가 어려웠다기 보다 내가 처음 고안한 풀이의 허점을 찾는데 너무 오랜 시간이 걸렸다. 며칠 전까지 그래프의 신이 되었나 하는 생각이 났었는데 지금 돌이켜보니 진아의 말대로 걍 한창 자신만만할 시기의 그 시기였던 거 같다. 그래서 오늘은 티어도 좀 올리고 그래프도 팔각형 각을 좀 세울겸 오랜만에 기하학 문제를 풀었다. 이분매칭 문제인데 기하학 태그가 달려 있어서 이게 웬 떡이냐 하고 풀었다. 간단하게 주석은 남겨두었고, 이만 줄이겠다.

import sys

def find_match(mouse):
    for hole in graph[mouse]:
        if visited[hole]:
            continue
        visited[hole] = 1
        if matched[hole] == -1 or find_match(matched[hole]):
            matched[hole] = mouse
            return 1
    return 0

N, M, S, V = map(int, sys.stdin.readline().split())  # N: 쥐의 수, M: 구멍의 수, S: 도약 거리, V: 속력
mice = [None] + [tuple(map(float, sys.stdin.readline().split())) for _ in range(N)]  # 쥐의 좌표
holes = [None] + [tuple(map(float, sys.stdin.readline().split())) for _ in range(M)]  # 구멍의 좌표

graph = [[] for _ in range(N + 1)]  # 쥐와 구멍의 연결 관계 그래프
for i in range(1, N + 1):
    for j in range(1, M + 1):
        if (mice[i][0] - holes[j][0]) ** 2 + (mice[i][1] - holes[j][1]) ** 2 <= S * S * V * V:
            graph[i].append(j)  # 쥐 i가 구멍 j로 이동 가능한 경우 연결

unmatched = N  # 탈출하지 못한 쥐의 수
matched = [-1] * (M + 1)  # 각 구멍에 매칭된 쥐의 번호
for i in range(1, N + 1):
    visited = [0] * (M + 1)  # 구멍 방문 여부
    unmatched -= find_match(i)

print(unmatched)  # 탈출하지 못한 쥐의 수 출력