DFS와 BFS

면접 대비

시간 제한2초메모리 제한128 MB

요약
주어진 무방향 그래프에서 시작 정점부터 DFS와 BFS로 방문하는 순서를 번호가 작은 정점을 우선하여 각각 출력합니다.
난이도

쉬움10점 중 3점

유형
DFS, BFS, 그래프
정답자
아직 제출이 없습니다

문제

주어진 그래프를 깊이 우선 탐색(DFS)으로 방문한 순서와 너비 우선 탐색(BFS)으로 방문한 순서를 출력하는 프로그램을 작성하시오. 다음에 방문할 수 있는 정점이 여러 개라면 번호가 가장 작은 정점을 먼저 방문한다. 더 이상 방문할 수 있는 정점이 없으면 탐색을 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 번호 V가 주어진다.

  • 1 <= N <= 1,000
  • 1 <= M <= 10,000

다음 M개의 줄에는 간선으로 연결된 두 정점의 번호가 주어진다. 같은 두 정점 사이에 여러 개의 간선이 있을 수 있다. 모든 간선은 양방향이다.

출력

첫째 줄에는 DFS로 방문한 순서를 출력하고, 둘째 줄에는 BFS로 방문한 순서를 출력한다. 각 줄에는 V에서 시작해 방문한 정점을 방문 순서대로 출력한다.

예제3

  1. 예제 1

    입력
    4 5 1
1 2
1 3
1 4
2 4
3 4
    예상 출력
    1 2 4 3
1 2 3 4

  2. 예제 2

    입력
    5 5 3
5 4
5 2
1 2
3 4
3 1
    예상 출력
    3 1 2 5 4
3 1 4 2 5

  3. 예제 3

    입력
    1000 1 1000
999 1000
    예상 출력
    1000 999
1000 999