7308 : 재귀 + BFS 결합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
그래프에서 DFS(재귀)와 BFS(반복문)의 탐색 순서를 비교하십시오.
DFS는 재귀 함수로, BFS는 큐(deque)를 이용한 반복문으로 구현합니다.
두 방법의 방문 순서 차이를 통해 각 탐색의 특성을 이해합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
DFS는 재귀 함수로, BFS는 큐(deque)를 이용한 반복문으로 구현합니다.
두 방법의 방문 순서 차이를 통해 각 탐색의 특성을 이해합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정점 수 $N$과 간선 수 $M$이 주어집니다. ($1 \le N \le 1{,}000$, $1 \le M \le 10{,}000$)
둘째 줄부터 $M$개의 줄에 간선 정보가 주어집니다.
둘째 줄부터 $M$개의 줄에 간선 정보가 주어집니다.
출력 설명
DFS: 로 시작하는 줄에 DFS로 방문한 정점 순서(재귀 호출 기준)를 출력합니다.BFS: 로 시작하는 줄에 BFS로 방문한 정점 순서를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4
1 2
1 3
2 4
2 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
DFS: 1 2 4 5 3
BFS: 1 2 3 4 5도움
같은 노드에서 인접 노드를 사전순으로 방문합니다. DFS는 재귀 호출, BFS는
from collections import deque를 사용합니다. 끊어진 컴포넌트는 번호 순으로 처리합니다.