가중치 없는 최단 경로를 위한 BFS
출발점에서 층별 거리를 계산합니다
가중치 없는 최단 경로를 위한 BFS은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
BFS가 하는 일
BFS는 그래프를 고리처럼 탐색합니다. 먼저 시작점을 방문하고, 그다음 한 단계 떨어진 모든 노드, 두 단계 떨어진 모든 노드 순서로 진행합니다. 🌊
고리 순서가 최단 경로를 보장하는 이유
BFS는 다음 고리로 넘어가기 전에 현재 고리를 모두 처리하므로, 어떤 노드에 처음 도달했을 때의 경로가 해당 노드로 가는 최단 비가중 경로입니다.
대기열이 핵심입니다
BFS는 대기열을 사용합니다. 먼저 들어온 것이 먼저 나갑니다. 새 이웃 노드는 뒤에 추가하고, 앞에 있는 노드를 다음에 처리합니다.
from collections import deque
q = deque([start])방문한 노드 추적하기
같은 노드를 두 번 대기열에 넣지 않도록 방문 표시를 유지하세요. 이렇게 하면 BFS가 빠르고 유한하게 동작합니다.
visited = [False] * (n + 1)
visited[start] = True거리 저장하기
거리 배열은 각 노드가 속한 층을 저장합니다. 시작점의 거리는 0이고, 모든 이웃의 거리는 부모보다 1만큼 큽니다.
dist = [-1] * (n + 1)
dist[start] = 0앞에서 꺼내기
각 단계에서 대기열의 앞에 있는 노드를 꺼내세요. 아직 처리하지 않은 노드 중 가장 가까운 노드이므로 바로 처리하면 됩니다.
u = q.popleft()이웃 확장하기
방문하지 않은 각 이웃 노드 u에 대해 방문 표시를 하고 거리를 설정한 다음 대기열의 뒤에 넣으세요.
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)전체 반복문
대기열이 빌 때까지 계속 꺼내고 확장하세요. 대기열이 비면 도달 가능한 모든 노드를 방문한 것입니다.
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)대기열에 넣을 때 표시하기
꺼낼 때가 아니라 대기열에 넣는 순간 방문 표시를 하세요. 늦게 표시하면 중복 노드가 대기열에 들어갑니다.
도달할 수 없으면 -1로 남습니다
BFS가 끝난 뒤에도 거리가 -1인 노드는 시작점에서 도달할 수 없는 노드입니다. 이 결과 역시 의미가 있습니다.
BFS의 시간 복잡도는 선형입니다
BFS는 모든 노드와 간선을 한 번씩 방문하므로 O(n + m)에 실행됩니다. 대부분의 대회 시간 제한을 충분히 통과할 수 있습니다.
빠른 확인
일반적인 BFS가 최단 경로를 제공하는 이유는 무엇인가요?
복습
BFS는 대기열과 거리 배열을 사용하여 실행합니다. 대기열에 넣을 때 방문 표시를 하고, 이웃을 확장한 뒤, 탐색이 끝나면 최단 거리를 읽으세요. 🎉
자주 묻는 질문
“가중치 없는 최단 경로를 위한 BFS” 강의는 무료인가요?
네 — “가중치 없는 최단 경로를 위한 BFS” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“가중치 없는 최단 경로를 위한 BFS”에서 뭘 배우나요?
출발점에서 층별 거리를 계산합니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“가중치 없는 최단 경로를 위한 BFS” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 입력에서 인접 리스트 만들기
- 가중치 없는 최단 경로를 위한 BFS
- DFS, 재귀와 반복 스택
- 연결 요소와 플러드 필