미로 탐색 > 문제은행

본문 바로가기


알고리즘 자료구조2

1912 : 미로 탐색

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



동현이는 방이 N개인 미로의 지도를 갖고 있다. 각 방에는 1번부터 N번까지 번호가 매겨져 있고, N개의 방 사이에는 M개의 문이 있으며, 각 문은 서로 다른 두 방을 연결한다. 동현이는 1번 방에서 출발해서 N개의 방을 모두 탐색해 볼 것이다.


동현이는 모험심이 강하기 때문에 항상 새로운 방을 찾기를 원한다. 동현이는 자신이 위치한 방과 연결된 방 중 한 번도 들르지 않은 방이 있다면 그 중 가장 번호가 작은 방으로 가고, 그렇지 않으면(연결된 방이 모두 전에 들렀던 방이면) 그냥 왔던 곳으로 되돌아가게 된다.

동현이가 N개의 방을 모두 방문하고 1번 방으로 오면 동현이는 탐색을 끝낸다. N개의 방을, 동현이가 먼저 방문한 순으로 정렬하는 프로그램을 작성하여라.


첫 번째 줄에는 방의 수 N과 문의 수 M이 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 500,000) 두 번째 줄부터 M개의 줄에는 각 문이 연결하는 두 방의 번호가 입력된다. 모든 방들은 문을 통해 연결되어 있고, 임의의 두 방 사이에는 최대 1개의 문이 있다. 전체 데이터의 38%는 2 ≤ N ≤ 3,000 이다.



첫 번째 줄에 동현이가 방문한 순서대로 N개의 방의 번호를 정렬하여 출력한다.


[Copy]
5 6
1 3
3 4
4 2
2 1
1 4
4 5
[Copy]
1 2 4 3 5



위 예제에 대한 미로의 지도는 다음과 같다. 이 때, 동현이는 1→2→4→3→4→5→4→2→1 순으로 미로를 탐색하게 된다.



출처 : functionx



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.