0-1 BFS 언제 쓰나, 다익스트라·Dial 판단표와 오답·시간 초과 점검

"벽을 최소 몇 개 부숴야 하나", "화살표를 최소 몇 번 바꿔야 하나" 같은 문제를 보면 0-1 BFS를 쓸지, 익숙한 다익스트라로 갈지 망설이게 되죠. 결론부터 말하면 비용이 0과 1 두 가지뿐이면 0-1 BFS, 0~k의 작은 정수면 Dial 버킷, 그 밖의 양수면 다익스트라예요. 그리고 0-1 BFS를 골랐다면 "비용이 칸에 붙는지, 이동 방법에 붙는지"를 한 번 더 확인해야 해요. 이 차이가 방문 표시를 어디에 둬도 되는지를 갈라요.

이 글은 덱 안의 거리가 왜 두 층으로 유지되는지 같은 원리는 짧게만 다뤄요. 대신 고를 때와 제출할 때 필요한 숫자와 확인 순서를 모았어요. 측정은 Apple M1, 파이썬 3.13.7, Apple clang 17(-O2)로 직접 했어요(2026-10-30). 절대 시간은 기기마다 다르니 배수로 읽어 주세요.

0-1 BFS 언제 쓰나, 가중치 모양별 판단표

어떤 최단 비용 알고리즘을 쓸지는 거의 간선 가중치 모양이 정해요. 그래프를 다 그린 뒤 가중치 종류를 세어 보는 게 첫 단계예요.

cp-algorithms의 0-1 BFS 문서도 0과 1로 제한된 경우를 O(|E|)로 풀 수 있다고 하고, 모든 가중치가 k 이하이면 버킷 k+1개로 넓힌 Dial 알고리즘을 쓸 수 있다고 정리해요. 같은 문서는 0 간선이 하나도 없으면 0-1 BFS가 일반 BFS로 바뀌고, 그때는 일반 BFS가 더 단순하고 조금 더 빠르다고 적어요.

문제를 0-1 그래프로 바꾸는 흔한 모양

문제 문장에 "0과 1"이 직접 나오지 않아도 이렇게 바꿔 보면 0-1 그래프가 되는 경우가 많아요.

• 벽 부수기: 빈 칸으로 가면 0, 벽 칸으로 가면 1. 비용이 도착 칸에 붙어요(LeetCode 2290 "Minimum Obstacle Removal to Reach Corner").
• 방향 바꾸기: 칸의 화살표대로 가면 0, 다른 방향은 1. 같은 칸이라도 들어오는 방향에 따라 비용이 달라서 비용이 간선에 붙어요(LeetCode 1368).
• 간선 뒤집기 최소 횟수: 방향 그래프의 원래 간선 u→v를 비용 0으로, 역방향 v→u를 비용 1로 추가해요. 정점 1에서 n까지 최소 비용이 곧 뒤집어야 할 간선 수예요.
• 무료 이동이 섞인 상태 그래프: 텔레포트·스위치처럼 공짜 전이는 0, 한 번 세는 이동은 1이에요.

반대로 "벽을 최대 k번까지 부술 수 있을 때 최소 이동 횟수"는 0-1 BFS 문제가 아니에요. 이동 하나하나가 비용 1이고 부순 횟수는 제약 조건이라, 상태를 (칸, 남은 횟수)로 늘린 일반 BFS가 맞아요. 상태 수 계산은 BFS DFS 판단표 글에 정리해 뒀어요. 묻는 것이 "최소 비용"인지 "비용 한도 안에서 최소 이동"인지부터 구분하세요.

0-1 BFS 구현 고르기, 덱·배열 두 개·힙 다익스트라 실측

같은 1000×1000 격자에 칸마다 벽을 무작위로 놓고(벽에 들어가면 비용 1), 왼쪽 위에서 오른쪽 아래까지 최소 부술 개수를 구했어요. 격자 둘레에 바깥 칸을 덧대서 경계 검사를 없앴고, 칸은 정수 하나(r × 폭 + c)로 표현했어요. 각 방식을 3번(파이썬)·5번(C++) 돌려 가장 빠른 값을 적었어요.

C++로 같은 실험을 하면(난수 생성기가 달라 격자 배치는 달라요) 힙의 비용이 더 크게 드러나요. 파이썬은 인터프리터의 기본 비용이 커서 힙 연산의 log 몫이 상대적으로 묻히거든요.

이 숫자로 판단하면 이래요.

• 덱과 배열 두 개는 사실상 같아요. 파이썬에서 1~2%, C++에서 4~21% 차이였어요. cp-algorithms 문서도 배열 두 개 방식이 덱보다 약 1.06~1.15배 빠르다고 적는데, 이번 측정도 그 범위 근처예요. 팀원이 읽기 쉬운 쪽을 고르세요.
• 다익스트라로 바꾸는 손해는 언어에 따라 달라요. 파이썬 약 2.2~2.9배, C++ 약 4.3~5.0배였어요. 제한 시간이 넉넉하면 다익스트라로 내도 되지만, 칸 400만 개 이상이거나 C++에서 다른 처리와 함께 돌린다면 0-1 BFS가 확실히 유리해요.
• "0 간선도 뒤에 넣기"는 반드시 피해야 해요. 아래에서 숫자로 다시 볼게요.

가중치가 0·1·2라면 Dial을 쓸까

같은 크기 격자에서 칸 비용을 0(50%)·1(30%)·2(20%)로 섞어 재 봤어요. 파이썬 heapq 다익스트라는 3.13초, 버킷 3개를 돌리는 Dial은 1.44초였고 답(141)은 같았어요. 약 2.2배 차이라 0-1 BFS와 다익스트라 사이의 차이와 비슷해요.

다만 Dial은 버킷 순환·빈 버킷 건너뛰기 코드가 붙어서 실수할 곳이 늘어요. 제한 시간이 빠듯할 때만 Dial로 바꾸고, 보통은 다익스트라로 충분해요. 비용 2짜리 간선을 중간 정점 하나를 끼운 비용 1짜리 두 개로 쪼개는 방법도 있지만, 정점 수가 늘어나는 만큼 메모리를 먼저 계산해 보세요.

방문 표시 위치, 비용이 칸에 붙나 간선에 붙나

0-1 BFS에서 가장 흔한 실수는 일반 BFS 습관대로 덱에 넣는 순간 방문 표시를 하는 거예요. 그런데 직접 돌려 보니 이 실수가 항상 오답을 내지는 않았어요. 비용 모양에 따라 결과가 갈렸어요.

실험은 2×2~8×8 무작위 격자 2,000개씩으로 했어요. 거리 비교로만 거르는 올바른 0-1 BFS를 기준으로, 넣을 때 표시 버전은 도착 칸 값을, 꺼낼 때 표시 버전은 거리 배열 전체를 비교했어요.

이유는 간단해요. 비용이 도착 칸에 붙으면 칸 u로 들어오는 모든 간선의 가중치가 같아요. 덱은 거리가 작은 정점부터 꺼내므로, u를 처음 발견한 정점이 곧 가장 가까운 이웃이에요. 그래서 첫 발견 거리가 최종값이에요. 비용이 간선에 붙으면 이 성질이 깨져요. 먼 이웃에서 비용 0으로 들어오는 길이 가까운 이웃에서 비용 1로 들어오는 길보다 쌀 수 있어서, 처음 발견한 거리가 나중에 줄어들어요.

실무에서 정리하면 이래요.

• 방문 배열 없이 d[v] + w < d[u] 비교로 거르는 것을 기본으로 하세요. 두 비용 모양 모두에서 맞아요.
• 방문 배열이 꼭 필요하면 꺼낼 때 확정 표시를 하세요. 꺼낸 정점이 이미 확정이면 건너뛰어요. 옛 사본을 다시 처리하지 않아 이웃 순회가 조금 줄어요.
• "넣을 때 표시"가 통과했다고 안심하지 마세요. 칸 비용형 문제에서는 우연히 맞았을 뿐이에요. 같은 코드를 간선 비용형 문제에 옮기면 틀려요.

0-1 BFS 비용 직접 계산, 삽입 횟수·힙 몫·메모리

판단할 때 쓸 수 있는 숫자를 몇 가지 계산해 둘게요.

삽입 횟수 상한은 정점당 2번이에요. 정점 u를 처음 발견했을 때 그 값은 "지금 꺼내는 거리 D 또는 D+1"이에요. 그 뒤에는 D보다 작아질 수 없어요. 그래서 u의 거리는 많아야 한 번 줄고, 덱에도 많아야 2번 들어가요. 화살표 격자의 1.12회는 이 상한 안에 있고, 0 간선을 뒤에 넣은 버전의 61회는 순서가 깨졌다는 뜻이에요. 디버깅할 때 삽입 횟수를 세는 줄 하나만 넣어도 이 버그를 바로 잡을 수 있어요.

힙 다익스트라가 더 내는 몫은 log V예요. 정점 100만 개면 log₂(10⁶) ≈ 20이에요. 힙에 넣고 뺄 때마다 비교·교환을 20단계 안팎 하는 셈이에요. 이번 격자에서는 다익스트라도 정점당 힙 삽입이 1.00회였어요. 그러니 C++에서 본 약 4.8배 차이는 거의 이 log 몫이에요.

"0 간선도 뒤에 넣기"가 느린 이유는 반복 완화예요. 이 코드는 거리 비교가 있어서 답은 맞아요. 하지만 덱이 거리순이 아니게 되어 한 정점이 거리가 줄 때마다 다시 들어가요. 벽 50% 격자에서는 정점당 61번, 실행 시간은 1.40초에서 105.30초로 약 75배가 됐어요. 작은 예제에서는 티가 안 나서 리뷰에서 놓치기 쉬워요.

메모리는 거리 배열과 덱이 전부예요. 덱에 동시에 드는 원소는 많아야 삽입 상한인 약 2V예요. C++ int 거리 배열은 정점 100만 개에 4MB, 덱도 최악 8MB 안팎이라 대부분의 메모리 한도에 여유가 있어요. 파이썬은 원소마다 8바이트 포인터가 붙고, 칸을 튜플로 넣으면 몇 배로 커져요. 칸을 정수 하나로 표현하세요.

0-1 BFS 오답·시간 초과 확인 순서, 체크리스트

제출이 틀리거나 시간 초과가 나면 이 순서로 봐요. 앞쪽일수록 흔하고 고치기 쉬워요.

1. 가중치가 정말 0과 1뿐인가. 입력 범위에 2 이상이나 음수가 있으면 0-1 BFS의 전제가 깨져요. 0과 2처럼 차이가 2인 경우도 안 돼요.
2. 비용이 칸에 붙나, 간선에 붙나. 시작 칸이 벽일 때 그 비용을 세는지가 문제마다 달라요. "도착 칸의 비용"으로 일관되게 정의하고, 시작 칸 비용이 필요하면 d[시작]에 미리 넣어요.
3. 방문 표시를 넣을 때 하고 있나. 간선 비용형이면 오답이에요. 표시를 지우고 거리 비교로 거르세요.
4. 0 간선을 앞에 넣고 있나. 삽입 횟수 ÷ 정점 수가 2를 넘으면 앞뒤가 뒤바뀌었거나 0 간선을 뒤에 넣고 있는 거예요.
5. 덱이 진짜 덱인가. 파이썬 collections 공식 문서는 deque가 양 끝에서 대략 O(1)로 넣고 빼지만, 리스트의 pop(0)·insert(0, v)는 O(n) 메모리 이동이 든다고 적어요. 자바는 ArrayList.remove(0) 대신 ArrayDeque를 쓰세요.
6. 작은 입력으로 다익스트라와 대조. 고친 뒤에는 칸 수가 작은 무작위 입력 수천 개로 거리 배열 전체를 비교해요. 도착 칸만 비교하면 놓치는 버그가 있어요.

6번은 이 정도 코드면 충분해요. 다익스트라는 가중치가 무엇이든 맞으니 기준 답으로 쓰기 좋아요.

import random

def check(solve, reference, trials=3000):
    rnd = random.Random(0)
    for t in range(trials):
        n = rnd.randint(2, 8)
        edges = [(rnd.randrange(n), rnd.randrange(n), rnd.randint(0, 1))
                 for _ in range(rnd.randint(1, 3 * n))]
        if solve(n, edges, 0) != reference(n, edges, 0):
            return t, n, edges   # 처음 틀린 입력을 그대로 돌려줘요
    return None

틀린 입력이 나오면 간선 수가 적은 것부터 손으로 따라가 보세요. 반례를 줄여 가며 찾는 방법은 그리디 반례 찾기 체크리스트에서도 같은 방식으로 다뤘어요.

도입 전에 따질 것, 라이브러리와 실무 그래프

코딩 테스트가 아닌 실무 코드에 0-1 BFS를 넣을 때는 몇 가지를 더 봐야 해요.

• 가중치 가정이 오래 유지되나. 요금 체계·규칙이 바뀌어 비용 2가 생기면 0-1 BFS는 조용히 틀린 답을 내요. 입력을 만들 때 assert w in (0, 1) 같은 검사를 넣거나, 처음부터 다익스트라로 두고 성능이 문제될 때만 바꾸세요.
• 라이브러리의 0 가중치 처리. SciPy csgraph 문서는 밀집 행렬 표현에서 0을 "간선 없음"으로 읽는다고 적어요. 가중치 0 간선이 의미 있으면 마스킹 배열이나 csgraph_from_dense(..., null_value=np.inf)로 만든 희소 행렬을 써야 해요. 그냥 csr_array(밀집 행렬)로 바꾸면 0 간선이 사라져요.
• 경로 복원이 필요한가. 거리가 줄 때마다 parent[u] = v를 함께 갱신해요. 재삽입이 있는 간선 비용형에서는 처음 발견한 부모가 최종 부모가 아닐 수 있어요.
• 출발점이 여러 개인가. 모든 출발점을 거리 0으로 덱에 넣고 시작하면 돼요. 출발점마다 따로 돌리면 시간이 출발점 수만큼 곱해져요.

자주 묻는 질문

0-1 BFS 대신 다익스트라를 내도 정답인가요?

네, 답은 같아요. 다만 이번 1000×1000 격자에서 파이썬은 약 2.2~2.9배, C++은 약 4.3~5.0배 느렸어요. 제한 시간이 빠듯하거나 칸이 수백만 개면 0-1 BFS로 바꾸세요.

0-1 BFS에서 방문 배열을 써도 되나요?

꺼낼 때 확정 표시를 하는 방식은 써도 돼요. 넣을 때 표시는 벽 부수기처럼 비용이 도착 칸에 붙는 문제에서만 우연히 맞고, 화살표 바꾸기처럼 비용이 간선에 붙는 문제에서는 무작위 격자 36.6%에서 틀렸어요. 기본은 거리 비교로 거르는 거예요.

덱과 배열 두 개 방식 중 무엇이 나은가요?

이번 측정에서는 파이썬 1~2%, C++ 4~21% 차이로 배열 두 개가 조금 빨랐어요. 제한 시간을 가를 정도는 아니니 익숙한 쪽을 쓰세요. 배열 두 개 방식은 현재 층이 비면 두 배열을 바꾸는 줄을 빠뜨리지 않게 주의하세요.

가중치가 0과 2이면 0-1 BFS를 쓸 수 있나요?

그대로는 안 돼요. 덱 안 거리가 두 층이고 그 차이가 정확히 1이라는 전제가 깨져요. 모든 가중치를 2로 나눌 수 있으면 나눠서 0-1 BFS를 돌리고 답에 2를 곱하면 돼요. 0·1·2가 섞이면 Dial 버킷 3개나 다익스트라를 쓰세요.

0-1 BFS가 시간 초과 나요. 무엇부터 보나요?

삽입 횟수를 세어 정점 수로 나눠 보세요. 2를 넘으면 0 간선을 덱 뒤에 넣고 있는 거예요. 이번 측정에서 이 실수 하나로 1.4초가 105초가 됐어요. 그다음 파이썬이면 큐가 deque인지, 칸을 튜플 대신 정수 하나로 표현했는지 확인하세요.

벽을 최대 k번 부술 수 있는 문제도 0-1 BFS인가요?

아니에요. 이동마다 비용 1이고 부순 횟수는 제약이라, 상태를 (칸, 남은 횟수)로 늘린 일반 BFS가 맞아요. "최소 몇 개 부수나"를 묻는다면 0-1 BFS, "k번 안에서 최소 몇 칸 이동하나"를 묻는다면 상태 BFS예요.

정리

• 가중치 모양으로 고르세요. 모두 같으면 BFS, 0과 1이면 0-1 BFS, 0~k 작은 정수면 Dial, 그 밖의 양수면 다익스트라예요.
• 덱과 배열 두 개는 거의 같아요. 다익스트라와는 파이썬 2~3배, C++ 4~5배 차이가 났어요.
• 방문 표시 대신 d[v] + w < d[u] 비교로 거르세요. 넣을 때 표시는 간선 비용형 문제에서 틀려요.
• 정점당 삽입이 2번을 넘으면 0 간선을 뒤에 넣고 있다는 신호예요. 작은 무작위 입력으로 다익스트라와 거리 배열 전체를 대조하면 남은 버그를 대부분 잡아요.
• 일반 BFS·DFS를 고르는 기준과 메모리·재귀 한계는 BFS DFS 언제 쓰나 판단표에 정리해 뒀어요.

더 깊이 읽기

이 글은 실무에서 판단할 때 필요한 것 위주로 정리했어요. 같은 주제의 내부 동작 원리는 devboi 기술 블로그의 0-1 BFS 원리 — 덱으로 가중치 0·1 최단 거리 구하기에서 도식과 코드로 단계별로 풀었어요.