0Pricing
Competitive Programming Academy · 강의

DFS, 재귀와 반복 스택

깊이 탐색하고 재귀 한도를 피합니다

DFS, 재귀와 반복 스택은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

DFS가 하는 일

DFS는 한 경로를 따라 가능한 한 깊이 내려간 다음 되돌아와 다음 경로를 시도합니다. 미로의 통로를 하나씩 탐색하는 모습을 떠올려 보세요. 🧭

DFS와 BFS 비교

BFS는 고리처럼 퍼져 나가고, DFS는 먼저 깊이 들어갑니다. 둘 다 도달 가능한 모든 노드를 방문하지만 방문 순서는 매우 다릅니다.

재귀 구조

재귀 DFS는 노드를 방문 표시한 다음 방문하지 않은 각 이웃에 대해 자기 자신을 호출합니다. 호출 스택이 돌아갈 위치를 기억합니다.

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

재귀하기 전에 표시하기

이웃을 탐색하기 전에 노드에 들어가는 순간 방문 표시를 하세요. 그렇지 않으면 순환 때문에 DFS가 무한 재귀에 빠집니다.

재귀 제한의 함정

Python은 재귀 호출을 약 1000회로 제한합니다. 깊은 그래프에서는 RecursionError가 발생하며, 실행 시간 오류 판정으로 나타납니다.

제한 늘리기

빠른 해결 방법 하나는 setrecursionlimit으로 제한을 높이는 것입니다. DFS를 실행하기 전에 최악의 깊이보다 크게 설정하세요.

import sys
sys.setrecursionlimit(300000)

대신 반복 방식 사용하기

가장 안전한 해결 방법은 직접 만든 스택을 사용하는 반복형 DFS입니다. 호출 깊이가 없으므로 재귀로 인한 충돌이 발생하지 않습니다.

stack = [start]

스택에서 꺼내기

각 단계에서 스택의 맨 위를 꺼내세요. 나중에 들어온 것이 먼저 나오는 방식 덕분에 DFS는 가장 최근 경로를 먼저 깊이 탐색합니다.

u = stack.pop()

이웃 넣기

u를 꺼낸 뒤 방문하지 않은 각 이웃 노드를 스택에 넣으세요. 다시 넣지 않도록 방문 표시도 하세요.

for v in adj[u]:
    if not visited[v]:
        visited[v] = True
        stack.append(v)

전체 반복형 반복문

스택에 노드가 남아 있는 동안 꺼내기와 넣기를 반복하세요. 스택이 비면 도달 가능한 모든 노드를 방문한 것입니다.

while stack:
    u = stack.pop()
    for v in adj[u]:
        if not visited[v]:
            visited[v] = True
            stack.append(v)

BFS와 같은 비용

BFS와 마찬가지로 DFS도 각 노드와 간선을 한 번씩 방문하므로 O(n + m)에 실행됩니다. 문제에 맞는 방문 순서를 기준으로 선택하세요.

빠른 확인

깊은 그래프에서 재귀 DFS가 충돌했습니다. 이유는 무엇인가요?

복습

DFS는 재귀 방식이나 직접 만든 스택으로 실행할 수 있습니다. 진입할 때 방문 표시를 하고, 그래프가 깊어지면 반복 방식으로 전환하세요. 🎉

자주 묻는 질문

“DFS, 재귀와 반복 스택” 강의는 무료인가요?

네 — “DFS, 재귀와 반복 스택” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“DFS, 재귀와 반복 스택”에서 뭘 배우나요?

깊이 탐색하고 재귀 한도를 피합니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

“DFS, 재귀와 반복 스택” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. 입력에서 인접 리스트 만들기
  2. 가중치 없는 최단 경로를 위한 BFS
  3. DFS, 재귀와 반복 스택
  4. 연결 요소와 플러드 필
← Competitive Programming Academy(으)로 돌아가기