프로그램 명: asteroid
제한시간: 1 초
[문제 요약] K ( 1 <= K <= 10,000) 개의 소 행성을 가진 N * N 격자가 있다.( 1 <= N <= 500 )
강력한 무기가 있어 한 번 발사에 한 행 혹은 열에 있는 모든 소 행성을 파괴할 수 있다.
모든 소행성을 파괴할 수 있는 최소의 shot 수를 구하는 것
Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The
grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid.
Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a
single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the location of all the asteroids in the
field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.
입력
- Line 1: Two integers N and K, separated by a single space.
- Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column
- coordinates of an asteroid, respectively.
출력
* Line 1: The integer representing the minimum number of times Bessie must shoot.
입출력 예
입력
3 4
1 1
1 3
2 2
3 2
출력
2
입출력 보충
입력은 3*3 그리드에 4 개의 소 행성이 있고 X 는 소행성의 위치
X.X
.X.
.X.
2 번의 shot 으로 모든 소행성을 파괴할 수 있다.
- 1 번째 행을 없애면 (1,1) 과 (1,3) 을 ,
- 2 번째 열을 없애면 (2,2) 와 (3,2) 를 파괴 가능하다.
출처: USACO 2005 November Gold
[질/답]
[제출 현황]
[푼 후(1)]