출발점에서 각 위치까지의 최소 비용을 확정하는 탐색
지도뿐 아니라 네트워크 지연, 작업 비용, 상태 전환 횟수처럼 ‘도달 비용’을 최소화하는 문제에 씁니다. 간선 비용의 조건에 따라 BFS 또는 다익스트라를 선택합니다.
코드를 생각하지 말고, 아래 상황이 어떤 순서로 움직이는지만 따라가 보세요.
가장 짧은 길이 아니라 신호와 정체 시간을 모두 더해 가장 빨리 도착하는 길을 골라 줍니다.
벽을 지나갈 수 없는 건물에서 출구까지 몇 칸만 이동하면 되는지 가까운 칸부터 확인합니다.
코딩 테스트의 장난감 예제를 넘어, 실제 시스템에서 같은 원리가 어디에 숨어 있는지 연결해 보세요.
출발지에서 목적지까지 거리·시간·요금이 최소인 경로를 찾습니다.
호출 그래프에서 누적 지연이 가장 작은 경로를 계산합니다.
장애물을 피하며 이동 횟수나 지형 비용이 최소인 경로를 찾습니다.
여러 도로의 거리와 통행 시간을 비교해 가장 빠른 배송 경로를 정합니다.
서버 사이 지연 시간을 합산해 요청이 가장 빨리 도착하는 경로를 고릅니다.
모든 간선 비용이 같으면 BFS의 레벨이 곧 최단 거리입니다. 비용이 서로 다른 비음수 간선에서는 다익스트라가 우선순위 큐로 가장 가까운 미확정 정점을 골라 거리를 완화(relax)합니다.
| 연산 | Python 표현 | 시간 |
|---|---|---|
| 무가중 최단 거리 | BFS | O(V+E) |
| 비음수 가중치 | Dijkstra + heap | O((V+E) log V) |
| 거리 완화 | new < dist[v] | 간선마다 |
| 경로 복원 | parent 저장 | O(V) |
dist[A]=0, 나머지=∞dist[B]=4, dist[C]=1C를 거치면 B=1+2=3 → 갱신최단 거리 A→C→B = 3설명을 닫고 먼저 풀어본 뒤, 막히는 지점에서 어떤 연산이 필요한지 다시 떠올려 보세요.
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으로 풀기