BFS DFS 언제 쓰나, 문제 유형별 판단표와 시간·메모리 초과 점검

그래프 문제를 보고 BFS로 갈지 DFS로 갈지 고민하다가, 막상 짜서 내면 시간 초과나 런타임 에러가 나는 경우가 많죠. 결론부터 말하면 "최단 거리·최소 횟수"를 묻는 순간 DFS는 후보에서 빠지고, 남은 건 가중치 모양(모두 같음 / 0과 1 / 그 밖)으로 BFS·0-1 BFS·다익스트라 중에서 고르면 돼요. DFS는 경로 모양(사이클, 위상 순서, 단절점)이 필요할 때 고르고요. 실제로 제출이 터지는 원인은 선택보다 큐 자료구조·방문 배열·재귀 깊이 같은 구현 비용 쪽이 더 흔해요.

이 글은 원리 대신 고를 때와 제출할 때 필요한 숫자만 다뤄요. Apple M1에서 파이썬 3.14.8, Apple clang 17(-O2), OpenJDK 24로 직접 쟀고(2026-10-26), 절대 시간은 기기마다 다르니 배수로 읽어 주세요.

BFS DFS 언제 쓰나, 문제 유형별 판단표

탐색 방법은 "무엇을 묻는가"와 "간선 비용 모양" 두 가지로 거의 정해져요. 출발점이 여럿이면 BFS 큐에 전부 넣고 시작하면 되고, 모든 경로 나열은 DFS 백트래킹이에요.

• 위상 정렬은 BFS로도 돼요. 진입 차수 0부터 큐에 넣는 칸 알고리즘은 재귀가 없어 깊이 걱정이 없고, 사전순 최소 순서가 필요하면 큐 대신 최소 힙을 써요.
• 간선이 늘며 연결 여부를 반복해 묻는다면 유니온 파인드를 쓰세요.
• 가중치가 모두 같은 양수 c이면 그냥 BFS예요. 간선 개수에 c를 곱하면 끝이에요.

실측 크기는 CSES 기준으로 잡았어요. Labyrinth는 격자 최대 1000×1000(칸 100만), Message Route는 정점 10⁵·간선 2×10⁵이고, 둘 다 1초·512MB 제한이에요.

BFS 큐 비용 직접 재기, deque와 list.pop(0)

파이썬 collections 공식 문서는 deque의 양 끝 연산이 O(1)에 가깝고, 리스트 pop(0)은 O(n) 이동 비용이 든다고 적어요. 이 비용은 "큐에 동시에 든 원소 수"에 비례해서 그래프 모양에 따라 티가 달라요. 1000×1000 빈 격자는 큐 최대 길이가 약 1,000이라 잘 드러나지 않지만, 정점 10만·간선 20만 무작위 그래프는 한 층이 40,420개까지 불어나 크게 느려져요.

자바는 ArrayList.remove(0)이 같은 함정이라 ArrayDeque를, C++은 std::queue나 배열 + 머리 인덱스를 써요.

언어별 속도 차이, 파이썬은 1초 안에 들어가나

같은 1000×1000 빈 격자 BFS를 C++(-O2, 배열 큐)로 돌리면 0.019초, 파이썬(deque, 넣을 때 표시)은 2.85초였어요. 약 150배 차이예요. 파이썬으로 칸 100만 개짜리 문제를 1초 제한에 맞추려면 다음 순서로 깎아요.

1. 좌표 튜플 대신 r * m + c 정수 하나로 칸을 표현해요.
2. 격자 둘레에 벽 한 줄을 덧대 경계 검사를 없애요.
3. dist 리스트 하나로 방문 표시를 겸해요(-1이면 미방문).
4. 그래도 모자라면 PyPy 지원 여부를 확인하고, 없으면 언어를 바꾸는 게 현실적이에요.

방문 표시를 꺼낼 때 하면 같은 격자에서 4.40초로 1.5배 느려졌어요. 넣는 줄에서 표시하세요.

방문 배열 메모리 계산, 무엇으로 표시하나

방문 표시 방식이 메모리를 몇십 배 바꿔요. 원소 100만 개를 tracemalloc으로 잰 값이에요.

• 칸 번호가 0부터 연속이면 리스트·bytearray를 쓰세요. 집합·딕셔너리는 해시 테이블 몫이 붙어 8~18배 커져요.
• 정점이 문자열 이름·큰 ID라면 먼저 0..V−1로 번호를 다시 매기고 배열을 써요.

인접 표현도 같은 계산이에요. 정점 10⁵개 인접 행렬은 1바이트씩이어도 10GB, 비트셋도 1.25GB예요. 파이썬 인접 리스트(간선 20만)는 22.5MiB였어요. MiB와 MB를 섞어 쓰면 숫자가 5% 가까이 어긋나 보이니, 한도와 비교할 땐 데이터 용량 변환기로 단위를 먼저 맞추세요.

상태 BFS는 곱셈부터

"벽을 k번 부술 수 있다"면 상태는 (칸, 남은 횟수)라, 1000×1000 격자에 k = 10이면 1,100만 개예요.

딕셔너리 값은 위 측정(100만 개에 70.5MiB)을 11배 한 어림이에요. 열쇠 6개 비트마스크면 상태가 칸 수 × 64라서, 1000×1000 격자에선 bytearray도 64MB예요. 곱셈 한 줄로 한도를 먼저 확인하세요.

0-1 BFS와 다익스트라, 언제 바꾸나

간선 비용이 0 또는 1이면 덱 앞뒤로 넣는 0-1 BFS가 O(V+E)로 끝나요. cp-algorithms 0-1 BFS 문서는 이 방법이 다익스트라의 O(E log V)보다 빠르고, 비용이 0~k 정수일 때는 버킷 k+1개로 넓힐 수 있다고 정리해요. 위 차트의 700×700 격자에서도 두 방식은 같은 답(98)을 냈고 시간은 약 2배 차이였어요.

• 비용이 0과 1뿐: 0-1 BFS. 힙이 없어 코드도 짧아요.
• 작은 정수(0~3 등): 버킷 방식도 되지만 2배 차이가 제한 시간을 가를 때만 바꾸고, 보통은 다익스트라로 충분해요.
• 실수·큰 정수: 다익스트라. 음수 비용: 벨만-포드 계열.

0-1 BFS에서 가장 흔한 실수는 방문 표시로 막는 거예요. "더 짧아졌을 때만 갱신"하는 거리 비교로 걸러야 해요.

양방향 BFS로 탐색량 줄이기, 효과는 얼마나

출발점과 도착점이 정해져 있고 그래프가 크면, 양쪽에서 한 층씩 번갈아 넓혀 가다 만나는 양방향 BFS가 효과적이에요. 분기 계수 b, 거리 d일 때 한쪽 BFS는 대략 b^d개를, 양방향은 2 × b^(d/2)개를 봐요(위키백과 Bidirectional search). 직접 재 본 값은 이래요.

조건은 까다로워요.

• 도착점이 하나여야 해요. 여럿이면 다중 출발 BFS가 맞아요.
• 거꾸로 가는 이웃을 셀 수 있어야 해요. 방향 그래프면 역방향 인접 리스트가, 퍼즐이면 역연산이 필요해요.
• 한 층을 통째로 넓힌 뒤 만남을 판정해요. 정점 하나에서 만났다고 바로 끝내면 최단이 아닐 수 있어요. 작은 쪽 프런티어를 먼저 넓히면 탐색량이 더 줄어요.

코딩테스트 크기면 한쪽 BFS로 대개 충분하고, 양방향은 수억 상태 퍼즐·소셜 그래프 거리 조회에서 값어치가 있어요.

재귀 DFS 깊이 한계, 언어별로 직접 재기

사슬 입력(1-2-3-…-n)에선 재귀 깊이가 정점 수만큼 쌓여요. 언어별로 직접 잰 결과예요.

• 파이썬 sys 공식 문서는 이 한도가 C 스택 넘침을 막는 장치이고, 너무 높이면 크래시할 수 있다고 적어요. 이번엔 순수 파이썬 함수끼리라 100만이 됐지만 C 확장을 거치는 재귀는 다를 수 있고, 167MB는 256MB 한도 환경에서 위험해요. threading.stack_size()로 스레드 스택을 키우는 우회책(0 또는 32KiB 이상)도 플랫폼마다 동작이 달라요.
• 자바 java 명령 공식 문서의 -Xss 기본값은 Linux/x64 1024KB, Linux·macOS Aarch64 2048KB예요. 채점 서버가 Linux/x64면 이번 측정보다 얕아요. 프레임 크기는 JIT 여부·지역 변수 수에 따라 달라져요.
• C++은 운영체제 스택 설정을 따르니 대회 규정을 먼저 확인하세요.

정점이 10만을 넘고 사슬 입력이 가능하면 처음부터 반복형 DFS로 짜세요. 꺼낼 때 방문을 검사하고 이웃을 거꾸로 넣으면 재귀와 순서가 같고, 후위 순서가 필요하면 스택에 "나감" 표시를 같이 넣어요.

운영에서 자주 나는 문제와 확인 순서, 체크리스트

앞쪽일수록 흔하고 고치기 쉬워요.

1. 큐가 진짜 큐인가. list.pop(0), ArrayList.remove(0), 큰 배열의 shift()를 찾아요.
2. 방문 표시가 넣는 줄에 있나. 큐에 넣은 횟수를 세어 정점 수를 넘으면 표시 위치가 틀린 거예요.
3. 재귀 깊이. 사슬 입력으로 재현해요. RecursionError, StackOverflowError, 종료 코드 139(세그폴트)가 신호예요.
4. 방문 배열의 모양과 상태 수. 튜플 집합·딕셔너리를 평탄한 배열로 바꾸고, 상태 BFS는 칸 수 × 상태 수를 곱해 봐요.
5. 입력 모양. 끊긴 그래프(−1 출력), 출발 = 도착(거리 0), 1부터 시작하는 번호(배열 n+1), 중복 간선·자기 루프를 작은 입력으로 하나씩 넣어 봐요.

고친 뒤엔 n이 10 이하인 무작위 그래프 수백 개로 전수 탐색 코드와 답을 대조하면 남은 버그를 대부분 잡아요. 같은 대조 방식은 투 포인터 버그 점검에도 정리해 뒀어요.

실무 서비스에서 탐색이 느릴 때

이웃을 DB·API로 가져오는 탐색(권한 트리, 의존성 그래프)이라면 이것부터 봐요.

• 이웃 조회가 정점마다 나가는지. 한 층을 모아 IN 절·배치 API로 한 번에 조회하면 왕복이 정점 수에서 깊이 수로 줄어요.
• 깊이 제한이 있는지. "친구의 친구까지"라면 그 층에서 멈춰요. 분기 계수가 수백이면 제한 없이는 끝나지 않아요.
• 사이클 가능성. 트리라고 믿고 방문 표시를 빼면 순환 참조 하나로 무한 루프예요.

도입 전에 따질 것

• 직접 짤지, 라이브러리를 쓸지. NetworkX의 single_source_shortest_path_length처럼 BFS 거리 함수가 이미 있어요. 정점 수십만 개 이하의 분석·배치 작업이면 라이브러리가 버그 위험이 적고, 수백만 정점이거나 응답 시간이 중요하면 배열 기반 구현을 검토하세요.
• 최악 입력 모양. 사슬(깊이 최대), 별(큐 폭 최대), 완전 그래프(E ≈ V²)를 한 번씩 돌려 봐요.
• 이웃 순서. 사전순 방문이 필요하면 인접 리스트 정렬 O(E log E)가 더 들어요(파이썬·자바 정렬 성능 판단표). 해시 집합을 순회하면 실행마다 순서가 달라질 수 있어 테스트 고정에 불리해요.

자주 묻는 질문

BFS와 DFS 중 코딩테스트에서 기본으로 무엇을 쓰면 되나요?

최단 거리·최소 횟수면 BFS, 사이클·위상 정렬·단절점이면 DFS예요. 도달 여부나 연결 요소 개수만 묻는다면 재귀 깊이 걱정이 없는 BFS나 반복형 DFS가 안전해요.

파이썬 BFS가 시간 초과 나요. 무엇부터 보나요?

큐가 deque인지부터 보세요. list.pop(0)이면 정점 10만 그래프에서 약 12배 느려졌어요. 그다음 방문 표시 위치와 좌표 튜플 사용을 확인하세요. 칸 100만 격자는 deque로도 약 2.9초라 1초 제한이면 PyPy나 다른 언어를 검토해요.

sys.setrecursionlimit만 크게 올리면 재귀 DFS가 되나요?

이번 측정(파이썬 3.14.8)에선 깊이 100만도 돌았지만 메모리를 약 167MB 썼어요. 공식 문서도 너무 높은 한도는 크래시를 부를 수 있다고 경고해요. 정점이 10만을 넘으면 반복형이 확실해요.

0-1 BFS 대신 다익스트라를 써도 되나요?

답은 같고, 700×700 격자에서 약 2배 느렸을 뿐이에요. 시간이 넉넉하면 익숙한 다익스트라를, 빠듯하면 0-1 BFS를 쓰세요.

상태 BFS에서 메모리 초과가 나요.

상태 수를 먼저 곱해 보세요. 1000×1000에 벽 부수기 10번이면 1,100만 상태라 bytearray로 11MB, 딕셔너리로는 약 800MB예요. 상태를 칸 번호 × (k+1) + 남은 횟수 정수 하나로 접어 평탄한 배열에 담으세요.

양방향 BFS는 언제 쓸 만한가요?

도착점이 하나이고, 거꾸로 이웃을 셀 수 있고, 그래프가 매우 클 때예요. 정점 20만 그래프에서 방문 정점이 약 106배 줄었지만, 층 단위로 넓히고 만남을 판정해야 최단 거리가 맞아요.

정리

• 고르는 기준은 "최단 거리를 묻나"와 "가중치 모양"이에요. 모두 같으면 BFS, 0과 1이면 0-1 BFS, 그 밖의 양수면 다익스트라, 탐색 트리 모양이 필요하면 DFS예요.
• 큐는 deque·ArrayDeque, 방문 표시는 넣는 줄, 방문 배열은 평탄한 bytearray·리스트로 잡으세요.
• 사슬 입력이 가능하면 재귀 대신 반복형 DFS로 짜세요.
• 상태 BFS와 인접 행렬은 곱셈 한 줄로 메모리 한도를 먼저 확인하세요.

더 깊이 읽기

이 글은 실무에서 판단할 때 필요한 것 위주로 정리했어요. 같은 주제의 내부 동작 원리는 devboi 기술 블로그의 BFS·DFS 원리 — 최단 거리 보장과 방문 표시 시점에서 도식과 코드로 단계별로 풀었어요.