Informatica Online Judge

  너비우선탐색 I [0171 / 00AB]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 568   Total Tried : 1627


The Champion of this Problem (C++) : gs17078 - ms / 385byte
My Best Submission (C++) : N/A

[]

Background

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



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

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


(원래 BFS는 한 정점을 방문하고 다음에 방문할 정점이 2개 이상일 경우에 어떤 정점을 방문해도 관계없지만, 이 문제에서는 채점의 편의를 위해서 번호가 작은 정점을 먼저 방문한다)


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

Input

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

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)
DATA수정(2019.12.12.) : JKJeong

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