간선 비용이 0 또는 1인 그래프에서 최단 거리를 구합니다. 0-1 BFS는 deque의 앞과 뒤를 어떻게 쓰나요?

꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →

잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?

답변과 점검 포인트 펼치기답변 접기

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

현재 노드에서 비용 0 간선으로 개선한 후보는 deque 앞, 비용 1 간선은 뒤에 넣어 가까운 거리 후보를 먼저 처리합니다. 일반 BFS의 첫 방문 고정 대신 거리 완화가 필요한 구현 규칙을 따릅니다.

0 비용 우회가 나중에 더 짧은 경로를 만들 수 있어 이미 발견됐다는 이유만으로 개선을 무시하지 않습니다. 오래된 후보와 중복을 처리하고 비음수 0·1 범위를 벗어나면 다른 알고리즘을 씁니다. 작은 그래프의 Dijkstra와 거리·도달성을 비교합니다.

이해가 드러나는 지점을 확인해 보세요.

현재 노드에서 비용 0 간선으로 개선한 후보는 deque 앞, 비용 1 간선은 뒤에 넣어 가까운 거리 후보를 먼저 처리합니다. 일반 BFS의 첫 방문 고정 대신 거리 완화가 필요한 구현 규칙을 따릅니다.
작은 그래프의 Dijkstra와 거리·도달성을 비교합니다.

놓치기 쉬운 조건과 오해를 짚어 보세요.

다음 핵심 구분을 반대로 설명하거나 성립 조건을 생략한다: 현재 노드에서 비용 0 간선으로 개선한 후보는 deque 앞, 비용 1 간선은 뒤에 넣어 가까운 거리 후보를 먼저 처리합니다.

하나 더 질문하며 이해의 범위를 넓혀 보세요.

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.