목표가 거리인지 구조인지 나눈다
최단 간선 수가 필요하면 BFS, 연결성이나 사이클 구조를 훑을 때는 DFS가 자연스럽다.
방문 표시 시점 결정
BFS는 queue에 넣는 순간 표시해야 같은 정점이 여러 거리로 들어오지 않는다.
그래프 표현을 맞춘다
간선 수가 적으면 adjacency list, 밀집 그래프나 빠른 존재 확인은 matrix를 고려한다.
BFS 거리
간선 수 최단
가중치가 모두 같을 때 먼저 도착한 거리가 최단이다.
가중치가 있으면 다익스트라를 본다.
DFS 재귀
깊은 경로
재귀가 문제 구조와 잘 맞지만 깊이 제한을 확인해야 한다.
큰 그래프는 반복 스택이 안전하다.
visited on push
중복 큐 방지
큐에 넣을 때 표시하면 같은 정점이 여러 번 들어가지
않는다.
거리 배열도 함께 설정한다.
parent
경로 복원
next를 방문시킨 이전 정점을 저장한다.
답 경로가 필요할 때만 둔다.
가중치 · 스택 깊이 · 초기화 점검
거리 BFS
dist.assign(n, -1);
dist[start] = 0; q.push(start);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int to : g[v]) if (dist[to] == -1) {
dist[to] = dist[v] + 1; q.push(to);
}
}