BFS/DFS 제출 점검

탐색 템플릿은 방문 시점과 출력 정책 고정

BFS와 DFS의 복잡도는 같아도 방문 체크 시점, 그래프 방향성, 인접 순서에 따라 결과와 성능이 크게 달라집니다.

01

방문 시점

BFS는 enqueue 직후 방문 처리하면 같은 정점이 큐에 중복 삽입되는 일을 줄입니다.

02

방향성

입력이 방향 그래프인지 무방향 그래프인지에 따라 간선 추가 방식이 달라집니다.

03

출력 순서

인접 리스트 정렬 여부가 요구 출력과 맞는지 문제 조건을 다시 확인합니다.

1

init

시작점과 멀티소스 초기 큐를 구분합니다.

2

mark

방문 표시 시점을 push/enqueue 직후로 고정합니다.

3

edge

방향성에 맞게 인접 리스트를 만듭니다.

4

case

순환, 고립, 단일 노드 반례를 돌립니다.