원숭이 사냥 > 문제은행

본문 바로가기


알고리즘 BFS2

2387 : 원숭이 사냥

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 20 회    시도횟수: 87 회   



당신은 숲속에서 당신의 간식을 빼앗아간 원숭이를 쫓고 있다. 원숭이가 워낙 기민하게 움직이지만, 당신은 세계에서 가장 좋은 머신건을 이용하여 원숭이를 잡을 수 있다.

 

원숭이는 잡히지 않기 위해 어떤 나무 뒤에 숨는다. 당신은 이러한 사실을 알고 있고 따라서 특정 나무를 골라서 그곳에 사격을 한다. 당연히 세계에서 가장 좋은 총이기 때문에 나무는 쉽사리 뚫리게 되며, 만약 원숭이가 그 나무 뒤에 숨어 있을 경우 원숭이는 총을 맞아 죽게 된다. 만약 원숭이가 사격한 나무에 없을 경우 원숭이는 사격 소리를 듣고 조용히 이웃의 나무(한 번에 바로 이동할 수 있는 나무)로 이동하게 된다. 워낙 기민한 원숭이기 때문에 당신이 알아채지 못하게 이동을 한다. 원숭이가 한 나무에 계속 숨지 않으며, 반드시 사격 후에 살아있을 경우에는 원숭이는 이웃한 나무로 이동하게 된다.

 

실탄이 별로 없기 때문에 모든 가능한 경우에 대해 사격 횟수를 최소화하여 원숭이를 잡고자한다.

 

 

306f86d6dd2bb6575dea0c5a3a0df2ef_1493863 

 

위의 그림에서 왼쪽 그림의 경우에는 둘 중에 한곳을 계속 사격하게 될 경우에 원숭이를 잡을 수 있다. 만약 원숭이가 처음에 그 나무에 없을 경우에는 다음 사격에서 죽게 된다. 오른쪽의 그림의 경우에는 원숭이를 절대로잡을 수 없는 경우이다.


입력은 여럿의 테스트 케이스로 이뤄진다. 테스트케이스 사이에는 빈 줄 하나가 입력된다. 테스트 케이스의 첫 번째 줄에는 나무의 개수 N(1≤N≤21)과 이웃한 나무의 쌍 M(0≤M≤210)이 입력된다. 만약 나무의 개수 N과 이웃한 나무의 쌍 M 모두 0 이 입력될 경우 이를 처리하지 않고 프로그램을 종료한다. 나무는 0번부터 N-1번까지 번호가 부여된다. 그 다음 줄부터는 M개의 줄에 0이상 N-1이하의 정수 a와 b가 공백을 사이에 두고 입력된다. 이는 a나무에서 b나무로 혹은 b나무에서 a나무로 바로 이동이 가능함을 뜻한다.



각 테스트 케이스에 대해 최악의 경우에 원숭이를 잡을 수 없을 경우에는 Impossible을 출력하며, 그렇지 않을 경우 다음과 같은 형식으로 출력한다. S: T1 T2 ... TS 여기서 S는 모든 경우에도 원숭이를 잡을 수 있게 하기 위한 최소의 사격 수고 Ti는 I번째에 사격해야 하는 나무의 번호를 뜻한다. 사격하는 순서가 여럿 있을 경우 사전 순으로 가장 빠른 것을 출력한다.


[Copy]
2 1
0 1

3 3
0 1
1 2
2 0

4 3
0 1
2 3
1 3
0 0
[Copy]
2: 0 0
Impossible
4: 1 3 3 1





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.