관계로 연결된 데이터를 빠짐없이 방문하는 BFS와 DFS
친구 관계, 도로, 의존성처럼 데이터의 핵심이 순서가 아니라 연결에 있을 때 그래프로 모델링합니다. BFS와 DFS는 연결 요소·경로·도달 가능성을 푸는 기본 탐색 엔진입니다.
코드를 생각하지 말고, 아래 상황이 어떤 순서로 움직이는지만 따라가 보세요.
역은 점, 역 사이 노선은 선입니다. 두 번만 갈아타면 갈 수 있는 역을 찾을 때 가까운 역부터 펼쳐 봅니다.
나와 직접 아는 사람을 먼저 보고, 그다음 그 사람들의 친구를 확인합니다.
코딩 테스트의 장난감 예제를 넘어, 실제 시스템에서 같은 원리가 어디에 숨어 있는지 연결해 보세요.
몇 다리 건너 아는 사람인지 찾고 연결 집단을 분석합니다.
상위 역할에서 상속되는 권한이나 하위 조직 전체를 탐색합니다.
링크를 따라 페이지를 방문하되 visited로 순환을 막습니다.
장비 연결 관계를 따라가며 끊어진 네트워크 구역을 찾습니다.
사용자가 본 작품과 연결된 비슷한 작품을 몇 단계 안에서 탐색합니다.
그래프는 정점과 간선으로 표현합니다. BFS는 큐로 가까운 정점부터, DFS는 스택이나 재귀로 한 경로를 끝까지 탐색합니다. 인접 리스트 기준 둘 다 O(V+E)입니다.
| 연산 | Python 표현 | 시간 |
|---|---|---|
| BFS | queue + visited | O(V+E) |
| DFS | stack/recursion + visited | O(V+E) |
| 인접 리스트 공간 | dict[list] | O(V+E) |
| 인접 행렬 공간 | V×V | O(V²) |
queue=[A], visited={A}B,C 예약 → queue=[B,C]D 예약 → queue=[C,D]방문 순서 A, B, C, D설명을 닫고 먼저 풀어본 뒤, 막히는 지점에서 어떤 연산이 필요한지 다시 떠올려 보세요.
Easy 연습 1 / 7
Python으로 풀기Easy 연습 2 / 7
Python으로 풀기Easy 연습 3 / 7
Python으로 풀기Easy 연습 4 / 7
Python으로 풀기Easy 연습 5 / 7
Python으로 풀기Easy 연습 6 / 7
Python으로 풀기Easy 연습 7 / 7
Python으로 풀기Medium 연습 1 / 3
Python으로 풀기Medium 연습 2 / 3
Python으로 풀기Medium 연습 3 / 3
Python으로 풀기