boj, 백준) 2191. 들쥐의 탈출 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/2191 2191번: 들쥐의 탈출 첫째 줄에 네 정수 N, M, S, V가 주어진다. 다음 N개의 줄에는 들쥐의 x, y좌표가 주어지고, 그 다음 M개의 줄에는 땅굴의 x, y좌표가 주어진다. 모든 좌표는 절댓값이 1,000을 넘지 않는다. www.acmicpc.net 2. 문제 개요 매에게 잡아먹히지 않기 위해 들쥐들은 땅굴로 도망가야 한다. 하지만 땅굴로 도망치는 속도가 있기 때문에 항상 모든 쥐들이 도망갈 수 있는 것은 아니다. 들쥐와 땅굴의 위치, 그리고 들쥐의 속도와 매가 도착하는 시간이 주어졌을 때, 잡아먹히게 되는 들쥐들의 최소수를 구하는 프로그램을 작성하자. 3. 문제 힌트 들쥐와 땅굴을 이분그래프로 만든다. 4. 문..
알고리즘/Bipartite matching
2020. 4. 8. 23:14