6089 : DFS 방문 순서 — 번호 작은 노드 우선
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
무방향 그래프와 시작 노드 S가 주어집니다. S로부터 출발하여 깊이 우선 탐색(DFS)을 수행할 때, 방문하는 노드의 순서를 출력하는 프로그램을 작성하십시오.
단, 한 노드에서 방문할 수 있는 인접 노드가 여러 개인 경우 번호가 가장 작은 노드를 먼저 방문합니다. 연결되어 있지 않아 방문할 수 없는 노드는 출력하지 않습니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 시작 정점 $V$: $1 \le V \le N$
• 인접한 정점이 여러 개이면 번호가 작은 것부터 방문합니다.
단, 한 노드에서 방문할 수 있는 인접 노드가 여러 개인 경우 번호가 가장 작은 노드를 먼저 방문합니다. 연결되어 있지 않아 방문할 수 없는 노드는 출력하지 않습니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 시작 정점 $V$: $1 \le V \le N$
• 인접한 정점이 여러 개이면 번호가 작은 것부터 방문합니다.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1,000)과 간선의 개수 M (0 ≤ M ≤ 10,000)이 공백을 사이에 두고 주어집니다.
둘째 줄부터 M개의 줄에 걸쳐 간선이 연결하는 두 정점 u와 v가 주어집니다.
마지막 줄에는 시작 노드 S (1 ≤ S ≤ N)가 주어집니다.
둘째 줄부터 M개의 줄에 걸쳐 간선이 연결하는 두 정점 u와 v가 주어집니다.
마지막 줄에는 시작 노드 S (1 ≤ S ≤ N)가 주어집니다.
출력 설명
시작 노드 S로부터 DFS를 수행했을 때의 노드 방문 순서를 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2
1 3
2 4
3 4
1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 4 3도움
파이썬으로 구현할 때 재귀 깊이 제한으로 인한 런타임 에러를 방지하려면
sys.setrecursionlimit을 충분히 설정해야 할 수 있습니다.