우주여행 > 문제은행

본문 바로가기


알고리즘 네트웤플로우

1882 : 우주여행

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 61 회    시도횟수: 520 회   



농부 창호가 키우는 소 중 가장 영리한 소 베시는 우주선을 타고 N x N(1≤N≤500)짜리 격자 안에 있는 위험한 소행성 구역을 지나가려고 한다.
그 격자 안에는 K(1 ≤ K ≤ 10,000)개의 소행성이 있는데, 편리하게도 모두 격자점 위에 위치하고 있다.


다행스럽게도, 베시는 강력한 무기를 가지고 있다. 그 무기는 어떤 주어진 행이나 열에 있는 모든 소행성을 한방에 증발시킬 수 있다.이 무기는 매우 비싸기 때문에 그녀는 이것을 알뜰하게 사용하기를 원한다. 구역 안에 있는 모든 소행성의 위치가 주어졌을 때, 베시가 모든 소행성을 제거하기 위해서 무기를 최소한 몇 번 사용해야 하는 지를 구하라.


입력의 첫 번째 줄에는 두 개의 정수 N, K가 하나의 공백으로 나누어져 들어온다.
두 번째 줄부터 K+1번째 줄에는 공백으로 나누어진 두 개의 수 R, C(1 ≤ R, C ≤ N)가 들어오며, 두 수 R, C는 각각 소행성의 행과 열을 나타낸다.


베시에게 필요한 최소한의 무기 사용 횟수를 출력한다.

[Copy]
3 4
1 1
1 3
2 2
3 2
[Copy]
2





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.