ALGORITHMS · CHAPTER 04
중급 · 50분그래프 탐색과 최단 경로
관계와 경로를 문제로 바꾸기
BFS·DFS를 구분하고, 가중치 조건에 따라 최단 경로 방법을 고른다.
CONCEPTS
개념을 문장으로 설명하기
그래프
정점과 정점 사이의 간선으로 관계를 표현하는 구조입니다.
예시
친구 관계, 지하철 노선, 웹 페이지 링크를 그래프로 모델링합니다.
CHECK방향·가중치 유무를 먼저 확인한다.
BFS
시작점에서 가까운 정점을 먼저 넓게 방문하는 탐색입니다.
예시
가중치 없는 그래프에서 처음 도달한 거리가 최단 간선 수입니다.
CHECK큐를 사용한다.
DFS
한 경로를 가능한 깊게 탐색한 뒤 되돌아오는 방식입니다.
예시
연결 요소, 사이클 탐지, 백트래킹 문제에 자주 쓰입니다.
CHECK재귀 또는 스택을 사용한다.
GUIDED PRACTICE
가중치 없는 최단 거리
A에서 D까지 간선 수가 가장 적은 길을 찾습니다.
- A를 거리 0으로 큐에 넣습니다.
- 큐에서 꺼낸 정점의 미방문 이웃을 거리+1로 표시해 뒤에 넣습니다.
- D를 처음 방문한 순간의 거리가 최단 간선 수입니다.
결론
같은 거리의 정점을 모두 처리한 뒤 다음 거리로 가므로 BFS가 최단 거리를 보장합니다.
ACTIVE RECALL · 4 STEPS
가리고, 말하고, 확인하기
읽기만 하지 말고 답을 떠올린 뒤 펼쳐 보세요.
01 · 정의 회상
“그래프”을(를) 보지 않고 한 문장으로 정의해 보세요.
02 · 비교 설명
“BFS”이(가) 필요한 상황을 예시와 함께 설명해 보세요.
03 · 핵심 점검
재귀 또는 스택을 사용한다.
04 · 풀이 재현
“가중치 없는 최단 거리”의 결론을 보기 전에 풀이 순서를 3단계로 다시 적어 보세요.
WORKBOOK · STEP BY STEP
개념 확인 문제
정답을 고르고 해설로 사고 과정을 확인하세요.
01
가중치가 모두 같은 그래프에서 최단 간선 수를 구할 때 적합한 탐색은?
02
DFS 구현에 자연스러운 자료구조는?
03
간선마다 비용이 다른 최단 경로에서 BFS만으로 충분하지 않은 이유는?
SPEAK IT OUT
면접 1분 답변 연습
BFS와 DFS의 방문 순서·자료구조·대표 활용을 비교해 보세요.
답변할 때는 정의 → 이유 → 짧은 예시 순서로 말해 보세요.공식·표준 자료로 더 읽기
Python docs · collections.deque원문 열기 ↗BFS 큐 구현에 자주 쓰이는 표준 덱 문서입니다.