Informatica Online Judge

  너비우선탐색 II [0172 / 00AC]

Time Limit(Test case) : 500 (ms)
Number of users who solved : 387   Total Tried : 440


The Champion of this Problem (C++) : gs13116 - 0ms / 286byte
My Best Submission (C++) : N/A

[]

Background

너비우선탐색(BFS)는 그래프의 임의의 한 정점에서 출발하여, 연결된 정점들 중 하나에 대해서 너비 순으로 먼저 탐색해 나가는 탐색법이다. 이 탐색방법은 장기, 체스, 미로찾기, 무가중치 그래프의 최단경로 탐색 등의 다양한 분야에 활용되는 알고리즘이다. 예를 들어 다음과 같은 그래프를 보자.



이 그리프에서 1번 정점에서 출발한 너비우선탐색 결과는 다음과 같다.

1-2-4-5-3-6-7


(단, 한 점정에서 갈 수 있는 곳이 여러 곳일 먼저 입력된 정점 부터 먼저 방문한다. FIFO 즉, 2 4, 2 3 순으로 입력되었다면 2번 정점에서 4번을 먼저 방문하고 나중에 3번을 방문하도록 작성해야 한다.)

문제에 주어지는 모든 그래프는 양방향 무가중치 그래프이다.

Input

첫 번째 줄에 정점의 수와 간선의 수가 공백으로 구분되어 입력된다. (단 정점은 2000개 이하, 간선은 10000개 이하임)
둘 째 줄부터 간선의 수에 해당되는 줄 만큼 한 줄에 한 간선의 출발점과 도착점이 공백으로 구분되어 입력된다.

Output

BFS순회 결과를 공백으로 구분하여 출력한다. (출발점은 1)

IO Example

입력
7 8
1 2
1 4
1 5
2 3
3 4
3 7
4 6
5 6

출력
1 2 4 5 3 6 7

DATA제작 및 정답제작 : 이승현(27th)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]