2039: 그래프 탐색(BFS)
[만든사람 : ]
문제 설명
그래프에서 탐색은 가장 기본적인 연산으로 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업이다.
많은 그래프 문제들은 정점의 탐색만으로도 해결될 수 있기 때문에 그래프 탐색 방법은 매우 중요하다.
기본적인 그래프 탐색 방법에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있다.
무방향 그래프의 정점과 간선이 주어졌을 때, DFS를 수행하며 방문하는 정점의 순서를 출력해보자.
많은 그래프 문제들은 정점의 탐색만으로도 해결될 수 있기 때문에 그래프 탐색 방법은 매우 중요하다.
기본적인 그래프 탐색 방법에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있다.
무방향 그래프의 정점과 간선이 주어졌을 때, DFS를 수행하며 방문하는 정점의 순서를 출력해보자.
입력 설명
첫째 줄에는 정점의 개수\(N (1 \le N \le 1000)\), 간선의 개수 \(M(1 \le M \le 10000)\), 탐색을 시작할 정점의 번호 \(V\)가 주어진다.
다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
출력 설명
DFS를 수행하였을 때, 시작 정점 V부터 출발하여 방문한 정점을 순서대로 출력한다.
입력 예시 Copy
4 5 1
1 2
1 3
1 4
2 4
3 4
출력 예시 Copy
1 2 3 4