덱을 이용한 0-1 BFS
가중치가 0 또는 1일 때 최단 경로를 찾습니다
덱을 이용한 0-1 BFS은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
특별한 그래프
간선 가중치가 0 또는 1뿐인 그래프도 있습니다. 이런 그래프에서는 더 단순하고 빠른 기법으로 다익스트라 알고리즘보다 좋은 성능을 낼 수 있습니다.
0-1 BFS 만나기
0-1 BFS는 0과 1로 가중치가 주어진 그래프에서 힙과 로그 항 없이 선형 시간에 최단 경로를 찾습니다.
도구: 덱
힙 대신 덱을 사용합니다. 덱은 앞과 뒤 양쪽에서 항목을 넣고 꺼낼 수 있는 큐입니다.
from collections import deque
dq = deque([src])핵심 통찰
가중치 0인 간선을 지나면 거리가 그대로지만, 가중치 1인 간선을 지나면 거리에 1이 더해집니다. 덱은 이 두 그룹을 순서대로 유지합니다.
가중치 0 간선은 앞에 넣기
가중치 0인 간선을 건넜나요? 비용이 추가되지 않으므로 이웃 노드를 다음에 처리하도록 appendleft로 덱의 앞에 넣습니다.
dq.appendleft(v)가중치 1 간선은 뒤에 넣기
가중치 1인 간선을 건넜나요? 시작점에서 한 단계 더 멀리 있으므로 이웃 노드를 append로 덱의 뒤에 넣습니다.
dq.append(v)앞에서 꺼내기
항상 현재 노드를 popleft로 꺼냅니다. 이렇게 하면 계층별 BFS와 마찬가지로 덱이 거리 순서로 정렬된 상태를 유지합니다.
u = dq.popleft()가중치로 완화하기
각 간선을 완화합니다. 새 거리는 dist[u]에 간선 가중치를 더한 값이며, 가중치에 따라 덱의 앞이나 뒤에 넣습니다.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = nd정렬 상태를 유지하는 이유
덱에는 동시에 서로 다른 거리가 최대 두 개만 들어 있습니다. 이 불변식이 있기 때문에 앞과 뒤에 나누어 넣는 방식이 작동합니다.
선형 시간의 속도
힙을 사용하지 않으므로 0-1 BFS는 O(V + E) 시간에 실행됩니다. 같은 그래프에서는 다익스트라보다 눈에 띄게 빠릅니다.
사용할 때
이동 비용이 없거나 1일 때 사용합니다. 일부 이동은 막혀 있고 나머지는 열려 있는 격자 등이 그 예입니다.
빠른 확인
가중치가 0인 간선을 통해 이웃 노드를 완화했습니다. 이웃 노드는 어디에 넣어야 하나요?
복습: 0-1 BFS
덱을 사용해 가중치 0인 간선은 앞에, 가중치 1인 간선은 뒤에 넣습니다. 그러면 O(V+E)의 깔끔한 선형 시간에 최단 경로를 구할 수 있습니다. ⚡
자주 묻는 질문
“덱을 이용한 0-1 BFS” 강의는 무료인가요?
네 — “덱을 이용한 0-1 BFS” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“덱을 이용한 0-1 BFS”에서 뭘 배우나요?
가중치가 0 또는 1일 때 최단 경로를 찾습니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“덱을 이용한 0-1 BFS” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 힙을 이용한 다익스트라
- 덱을 이용한 0-1 BFS
- 벨만-포드와 음의 간선
- 플로이드-워셜 모든 쌍 최단 경로