물먹는 용(Enter The Dragon) > 문제은행



알고리즘 자료구조2

1285 : 물먹는 용(Enter The Dragon)

제한시간: 3000 ms    메모리제한: 128 MB
해결횟수: 44 회    시도횟수: 261 회    Special Judge



아데니아의 수도는 여러 개의 도시로 이루어져 있다. 각 도시는 하나의 호수를 갖고 있으며 호수 주변에 형성되어 있다. 최근 많은 비가 내릴 것으로 예상되는데 각각의 도시는 호수의 물을 비우면 홍수가 나지 않지만 호수를 비우지 못한 도시는 홍수피해를 입게 된다. 초기에 모든 호수에는 물이 차 있다.


그런데 다행스럽게도 아데니아에는 전설의 물먹는 하마 아니 물먹는 용 참견스가 살고 있다고 한다. 여러분도 알다시피 참견스는 호수 옆에 앉아 한번 들이키면 호수의 물을 모두 말라 버리게 할 수 있다. 참견스의 배는 무한대라서 얼마든지 호수를 비울 수 있지만 비가 내리는 날에는 어느 호수의 물도 마시지 않는다고 한다. 아데니아에는 예언자가 있어 오늘 이 후 여러 날 동안의 날씨를 예측할 수 있다고 한다.

 

여러분이 해야 할 일은 예측된 일기 예보가 주어질 때, 어느 날에 어느 호수의 물을 참견스가 먹어야 할지 계산하는 것이다. 


입력은 4개의 TestCase로 구성되며 각 TestCase의 구성은 다음과 같다.

첫 행에 호수의 개수 N과 M( 1 <= N, M <= 10^6)이 공백으로 구분하여 주어진다.
N은 호수의 수이고 M은 예측된 일기 예보의 개수이다.
두 번째 행에 M개의 정수 P_k가 공백을 구분하여 주어진다. 
P_k가 0인 경우에는 k번째 날에는 비가 오지 않는 날이고 
P_k가 1인 경우 k번째 날에는 1번 호수에, 
P_k가 2인 경우에 k번째 날에는 2번 호수에 등등... 비가 내린다.


아데니아의 모든 도시에 홍수가 발생하지 않는 경우 
첫 행에 YES를 출력하고 다음 행에는 비가오지 않는 날에 참견스가 호수의 물을 마시게 되면 호수의 번호를,
마시지 않을 경우에는 0을 공백을 구분하여 출력한다.
가능한 경우가 여러 가지라면 그 중 한 가지만 출력한다.
어느 한 도시라도 홍수가 발생하면 첫 행에 NO만 출력한다.

2 4
0 0 1 1
2 4
0 1 0 2
2 3
0 1 2
2 4
0 0 0 1
NO
YES
1 2
NO
YES
0 1 0





set, map, union-find

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.