♟ 그래프 순회를 위한 전략, DFS/BFS 탐색 알고리즘

관련글 :

다익스트라	https://waydd.tistory.com/13
DP	https://waydd.tistory.com/92
완전 탐색	https://waydd.tistory.com/97
사이클 판별, 개수 (DFS)	https://waydd.tistory.com/51
유니온 파인드	https://waydd.tistory.com/29
모든 조합, 순열 구하기	https://waydd.tistory.com/108
백트래킹 문제	https://waydd.tistory.com/107
위상 정렬	https://waydd.tistory.com/101
인접 리스트 배열 초기화	https://waydd.tistory.com/153

 

 

1. DFS (Depth-First Search, 깊이 우선 탐색)

 

시작 노드에서 한쪽 경로의 끝까지(최대한 깊이) 탐색한 뒤, 더 이상 갈 수 없으면 이전 단계로 돌아가며 모든 노드를 탐색하는 방식

→ 한 방향으로 깊게 들어가며 백트래킹으로 되돌아옴

※ 백트래킹(backtracking)? 더 이상 진행할 수 없을떄 되돌아가는 방식(= 뒤에서 부터 가지치기)  (DFS 핵심 구조)

• 스택(배열, 리스트) 또는 재귀 사용
  → 경로를 따라 깊이 들어가기 위함, 모든 경로를 따라가서 방문 여부 확인이나 탐색 순서 기록
• 무한 루프를 방지하기 위해 visited 로 방문 체크 (중복 방문 방지)
• 연결 그래프일 경우, 한 정점에서 DFS를 시작하면 모든 정점에 도달 가능
  → 비연결 그래프일 경우, 어떤 정점에서는 DFS로 모든 정점에 도달 불가 (모든 정점에 대해 반복 수행해야 함)
• 메모리 사용 적음(깊이만큼만 노드 저장), 출구가 깊은 곳이면 빠름
  
• 큰 입력에 비효율적 (= 탐색 순서 때문), 실패할 수도 있음(= 재귀 때문)
  → 재귀 깊이 제한(≤1,000)으로 인한 스택 오버플로우(= RecursionError) 주의 (제한 명시적으로 늘려줘야 안전) 
  → 스택 구조상 호출(콜 스택)이 쌓여서 메모리 부담 큼 
  → 그래프가 일자로 불균형 구조(중첩 연결) + 목표가 일자 경로에는 없지만 얕은 곳 : 불필요한 깊은 경로까지 탐색해야 함
• 희소그래프(간선이 적음)일수록 유리, 때문에 주로 인접 리스트 사용
• 최단 거리 보장 ❌, 가능한 모든 경로 탐색에 적합
  → 모든 경로를 다 탐색 후 최소값을 비교해야함 (비효율)
• 시간 복잡도(전체 순회): O(V + E)  (V: 정점 수, E: 간선 수)
  → 모든 정점과 간선을 한 번씩 방문하므로
• 공간 복잡도 : O(V): visited 배열(공간) 또는 재귀 호출 스택(스택 깊이)
  → 그래프가 선형 구조일떄 최악 O(V)
• 해가 유일하거나 최적화가 아닌 탐색 중, 원하는 결과를 찾으면 즉시 탐색 종료하거나 그래프 전체를 탐색하는 문제에 사용
  → 재귀 호출 순서 구조 : 순서를 보장, 호출 후 리턴하면서 결과 처리(후처리) 적합
  → 백트래킹 구조 : 모든 조합, 순열, 부분집합 생성에 최적화, 완전탐색 기반
  → 아래는 후처리 방식에 따라 정리
  ※ 조기 종료형 문제 유형 ( 목표 달성 시 break )

  경로 유무 탐색	특정 노드까지 도달 가능한지(= 존재 여부) → DFS/BFS 모두 가능, 목표 노드가 어디쯤에 있는가에 따라 선택  (이론 성능 O(V+E) 동일) → BFS보다 메모리 적게 쓸수있음
  미로 찾기	위와 같은 방식, 탈출 여부만 (탐색 순서 때문에 최단경로는 아님)
  그래프 사이클 판별 (존재 여부)	이미 방문한 노드를 다시 방문하려고 할 때 부모 노드가 아니라면 사이클 → 방향 그래프에선 back-edge 감지 필요 (무방향 한정 유니온 파인드가 더 효율적)

  ※ 조건부 탐색형 문제 유형 ( 조건(중복/순서 고려), 비용 갱신 있음(최소최대값, 정답수) → 재귀 방식 유용(분기 탐색) )

  백트래킹 (조건 만족 조합만 찾기)	①  N-Queen ②  부분 수열의 합이 특정 값  (DP가 더 효율) ③  최소 비용 경로 찾기  (최악 O(2^N), 입력 커지면 다익스트라, DP이 효율)
  모든 조합/순열 구하기	백트래킹 이지만 모든 경우 탐색
  그래프 사이클 판별 (경로 저장, 개수)	끝까지 탐색하며 조건 만족 여부 추적

  ※ 전체 탐색형 문제 유형 ( 모든 노드 방문 후 처리 → 재귀 방식 유용(방문 후 후처리 필요) )
  

  연결 요소 개수 구하기	방문하지 않은 모든 노드에 대해 DFS 수행 → 전체 그래프 완전 탐색 필요 → BFS도 효율적, DFS가 더 자주 쓰임 (∵ 구현 간결, 간단한 재귀 처리) ※ 왜 전범위 탐색해야하는지 (2번 문제) : https://waydd.tistory.com/135
  위상 정렬 (DFS 버전)	후처리 중심 알고리즘, 그래프의 모든 노드를 방문해야 하며, 후위 순회 결과를 뒤집어 정렬 생성
  트리 탐색 (후위 순회)	스택 진입 시점, 재귀 흐름, 스택 종료 시점은 각각 전위, 중위, 후위 순회 구조와 일치 → 한번의 탐색으로 가능 (사이클이 없음)

# (정석) 방문 집합을 외부에서 넘김(재사용성)
def dfs_recursive(graph, start, visited): 
    visited.add(start)  # 진입하면 즉시 방문 처리
    print(start)
    
    for neighbor in graph[start]:  # 재귀 진입 조건
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

visited = set()
dfs(graph, 1, visited)

※ DFS 탐색 흐름
①  시작 노드 선택
②  방문 처리 (visited 표시) → visited.add(start)
③  인접 노드들 중 방문 안한 노드 재귀 호출 → for neighbor in graph[start]: if ...
④  모든 인접 노드를 다 방문했으면 되돌아감
⑤  다시 상위 노드에서 다른 인접 노드 탐색

※ 방문 체크를 집합 대신 리스트로 하는 경우
- 외부 인자의 초기화 : ex) visited = [False] * 6
- 방문 처리 : visited[start] = True
- 방문 확인 : if not visited[node]:
위에 대응하는 코드를 변경하면 됨

※ 백트래킹 구현이 유리한 이유
- DFS에서 재귀 호출이 끝난 후 자동으로 이전 상태로 돌아감 (상태 복원 코드가 필요 없음)
- 조건 가지치기 (Pruning) 쉬움 
  → 깊이 들어가기 전/도중에 조건 체크로 불필요한 탐색을 중단할 수 있음
- BFS에서도 구현이 가능하나 코드 복잡(상태 복원) + 상태 추적이 어려움(직관성이 떨어짐)
  → 큐에서 (상태, 경로)를 계속 넣고 꺼냄, 반복

※ 전체 탐색에 유리한 이유
①  깊이 우선 탐색 구조 : DFS는 하나의 선택을 끝까지 가지고가는 방식, 전체 경우의 수를 만들기 유리
②  재귀 호출 구조 + 백트래킹 : 재귀를 통해 상태를 기억하면서 탐색 + 조건 불만족 시 되돌아가기가 쉬움
③  스택(또는 재귀)를 통해 자연스러운 분기 탐색 : 매 단계마다 선택-진행-복귀(백트래킹) 패턴을 쉽게 구현 가능
④  메모리 효율적 : BFS와 달리 한 경로만 기억하면 됨 → 메모리 사용이 적음 (특히 조합/부분집합 생성 시)
→ 모든 경우의 수를 체계적으로 생성하고 탐색하는 데 적합

※ 조합 생성 문제에 유리한 이유
- 조합? 어떤 원소 집합에서 특정 개수만큼 뽑는 모든 경우의 수를 만드는 것
  ex) [1, 2, 3] 중에서 2개 모든 조합 → (1,2), (1,3), (2,3)
- DFS는 상태를 깊게 들어가면서 탐색 + 백트래킹 구조를 갖고 있어서
- 때문에 경우의 수를 만들어야 할 경우, 깊이 탐색하면서 조합, 순열(순서 유지), 부분집합 생성 가능, 최적화

 

 

- 내부에서 방문 집합 다루는 경우

# 내부에서 방문 집합을 처리
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()  # 항상 함수 호출 시점에서 새로 생성됨

    if node not in visited:  # 로직이 실행될지 여부가 맨 위 조건에 의존
        print(node, end=" ")  # 방문 순서 출력
        visited.add(node)

        for neighbor in graph[node]:  # 인접 노드 탐색
            dfs_recursive(graph, neighbor, visited)

# DFS 실행, 시작노드 1
dfs_recursive(graph, 1)

※ 함수의 매개변수에서 visited를 생성하는 경우 (None이 아닌)
  def dfs_recursive(graph, node, visited=set()): 
  ...
- 위처럼 set() 객체는 처음 이 함수가 정의될 때 한 번 생성 
- if visited is None: 이 아닌  if node not in visited: 으로 기존 반복체크 + 내부 방문 집합의 빈 상태를 검사함
- 하지만 Python 기본 인자 동작 방식에 의해 다시 재호출했을 경우, 사용된 visited가 다시 재사용되므로 원하지 않은 결과가 나올수 있음
- 단 한번의 함수  호출을 쓰고자 한다면 사용 가능

 

 

- 반복문(스택) 방식

• 재귀 대신 스택을 직접 사용 → RecursionError 방지 가능
• 재귀 DFS와 논리적으로 동일
• 방문 순서는 스택에 넣는 순서에 따라 달라짐 (reversed() 중요)

# (정석) 하지만 스택에 이미 방문한 노드도 들어갈 수 있음 (필터는 됨)
def dfs_stack(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")

            # 스택은 후입선출, 인접 노드를 역순으로 넣기 = 재귀 구조와 동일
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

dfs_stack(graph, 1)

# 간결 함수형 스타일,  리스트 컴프리헨션으로 스택에 한꺼번에 push

def dfs_stack(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()  # 스택에서 노드 꺼내기
        if node not in visited:
            visited.add(node)

            print(node, end=" ")  # 방문 순서 출력

 

            # 스택에 인접 노드 추가, 오른쪽부터 방문 (= 인접 노드를 역순으로 넣어야 원래 재귀 순서와 동일함)
            # stack.extend(reversed(graph[node]))  # ← 이미 방문한 노드도 포함됨

            # 아래는 방문하지 않는 노드만 스택에 쌓음, 스택 크기 Down & 성능 살짝 향상(개선)
            stack.extend(reversed([neighbor for neighbor in graph[node] if neighbor not in visited])) 

※ 또 다른 방문 검사 방식
- 위는 방문 여부를 조건문으로 진입 제한하는 조건 진입형 (if not visited: then)
- 선제 조건 차단형 (if node in visited: continue)는 방문 여부를 명시적으로 우선 필터링
- 둘다 성능 동일, 선호에 따라 쓰기

 

 

2. BFS (Breadth-First Search, 너비 우선 탐색)

 

시작 노드에서 먼저 가까운 노드부터 순차적으로, 점차 탐색 범위를 넓혀가며 모든 노드를 탐색하는 방식

→ 현재 노드의 모든 인접 노드 탐색(방문) 후, 다음 깊이로 진행(= 같은 깊이의 노드를 먼저 탐색)  (계층적, 레벨 순 탐색)

• 큐 사용 (FIFO 방식으로 방문 순서 보장) → collections.deque 사용 (queue.popleft())
  
• 한 레벨씩(거리 1 → 거리 2 → …) 확장 탐색
• visited 방문했는지 여부 저장 필요 (무한 루프 방지)
• 비연결 그래프일 경우, 모든 정점에 대해 BFS 반복 수행 필요 ( DFS랑 동일)
• 메모리 사용 많음(큐로 많은 노드 저장), 출구가 가까우면 빠름
• DFS보다 큰 입력에서 안정적, 효율적 (너비가 아주 넓지 않은 그래프에 한하여)
  → 반복문 기반이므로 재귀 깊이 제한 없음
  → 큐에 많은 노드가 들어가도 일반적으로는 안전 (메모리 사용량 증가 가능성은 존재)
  ex) 트리에서 노드 100만개는 가능, 완전 이진 트리에서 깊이가 30 이상(큐에 한번에 최대 10억개)인 경우 메모리 오버 가능성 있음
• 최단 거리 보장 ⭕(비가중치 혹은 가중치 모두 1) → 최단 거리 탐색에 적합
  ※ 가중치가 다르면 다익스트라 같은 알고리즘을 써야 함 (아래 추가 설명)
  
• 속도 느릴 수 있음 (모든 경우 확인)
  → DFS 는 한 경로를 끝까지 탐색, 조건에 따라 가지치기 쉬움
  → BFS는 모든 레벨의 노드를 한꺼번에 큐에 넣어서 탐색 공간이 넓음
  → 조건 여부와 무관하게 큐에 들어간 노드를 처리해야 함
• 시간 복잡도 : O(V + E)
• 공간 복잡도 : O(V)
  → 큐에 레벨별로 저장
• 해 유일 X, 최적화 아닌 탐색 중, 주로 그래프 전체를 탐색하는 문제에 다수 사용
  → 가장 먼저 도달(최단거리)하거나 탐색 단계(레벨)의 순서가 중요한 경우 적합  (거리 기반 탐색)
  → 2차원 격자, 미로, 상하좌우의 이동이 주어졌을때 역시 사용
  → 아래는 후처리 방식에 따라 정리 (탐색 범위가 아님)
  ※ 조기 종료형 문제 유형 ( 목표 달성 시 break )

  최단 거리 찾기 (그래프, 미로 탈출)	출구에 가장 먼저 도달하는 경로 찾기 (가중치 X일때 최단 거리 보장)
  최소 이동 횟수/단계 (목적지 있음)	연산, 말 이동 등에서 목표 수/위치에 가장 빨리 도달할 때까지 카운트

  ※ 조건부 탐색형 문제 유형 ( 매번 BFS 전체 수행, 조건 만족 시 분기  )

  최적 조건 지점 찾기	여러 후보에서 BFS를 반복, 조건만족 여부 비교 후 첫 지점 찾기
  최소 거리 합 위치 선정(거리 합 최소화)	특정 위치에서 모든 집까지의 거리 합이 최소인 지점 찾기 (모든 지점 거리 합 계산, 최솟값 찾는 구조)

  ※ 전체 탐색형 문제 유형 ( 큐/스택이 빌 때까지 상태를 누적, 갱신, 기록 )

  맵 탐색/영역 탐색	지도에서 모든 구역(육지, 섬, 영역 등)을 BFS로 탐색하여, 카운트 or 영역
  최단 거리 전체 구하기 (그래프 거리 배열 구하기)	시작점에서부터 모든 노드까지의 최단 거리/레벨 구하기 (가중치 X일때)
  가장 멀리 떨어진 노드 찾기	시작 노드로부터 거리(간선 수)가 가장 먼 노드 탐색 (모든 노드 거리 계산 후, 최댓값)
  최초 감염/전파 도달, 최소 이동 횟수/단계 (목적지 없음)	모든 노드(또는 좌표)에 대해 감염 or 신호가 특정 노드에 처음 도달하는 순간을 기록, 보통 격자(맵, 토마토, 감염 등) 형태
  전염 문제(감염 확산), 토마토 문제	감염 인접 노드로 전파 → 감염 카운트, 모든 지점 감염 여부 판별 (-1로 실패 반) + 몇 시간(또는 며칠) 후에 전체에 전파되는지 계산 (모든 칸 확인 필요)
  위상 정렬	모든 노드 정렬된 순서로 나열해야함 (진입 차수 0부터 큐로 전개)
  레벨 순회 문제	트리, 그래프의 레벨 순회 출력

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()  # 큐에서 노드 꺼내기
        print(node, end=' ')  # 방문 순서 출력

        for neighbor in graph[node]:  # 인접 노드 탐색
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

※ BFS 탐색 흐름
①  시작 정점을 큐에 삽입하고 방문 처리
②  큐에서 정점을 꺼냄 → node = queue.popleft()
③  꺼낸 정점의 인접 정점들을 확인 → for neighbor in graph[node]:
④  아직 방문하지 않은 인접 정점을 큐에 추가하고 방문 처리
⑤  큐가 빌 때까지 2~4를 반복

※ 서로 다른 가중치가 있는 경우, 최단 거리 찾기 (= 최소 비용 찾기)
(예시) 1 --(10)--> 2, 1 --(1)--> 3 --(1)--> 2
BFS는 1→2 경로(거리 10)를 먼저 발견하지만, 실제 최단 거리는 1→3→2 (거리 2)
- 레벨 = 거리 (BFS) 가 더 이상 성립 X
- 가중치(양수) 그래프: 다익스트라(우선순위 큐 기반)가 최소 비용 보장
  → DFS+백트래킹은 가능하지만 비효율적일 수 있음 (가중치가 크고 범위가 크며, 경로 수가 많은 경우)
- 격자 기반 문제: DP로도 효율적 풀이 가능 (오른쪽/아래만 이동 시)
- 그외 벨만-포드, A* 등의 알고리즘을 사용

 

 

- visited 외부에서 전달 + defaultdict 사용한 그래프 표현 (인접 리스트)

• visited 자료구조로 리스트 or 딕셔너리 사용 가능 (아래는 리스트)
  → list는 노드의 개수를 알고 있으면/노드가 정수일때 용이

from collections import deque, defaultdict

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        node = queue.popleft()
        print(node, end=' ')  # 또는 result.append(node)

        for neighbor in graph.get(node, []):  # dict에서 안전하게 접근
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

※ defaultdict가 아닌 dict로 인접 리스트를 표현하고 있다면
①  for neighbor in graph[node]:
②  for neighbor in graph.get(node, []):
- ②번이 없는 노드 접근도 안전하게 처리하기 때문에 안전

 

 

3. visited와 부가 정보 관리 + 결과 수집 패턴

 

- 문제 풀이 절차 (순서대로)

• 입력 파싱
• 전처리
  → 불필요한 값 제거, 정렬, 인접 리스트/DP 배열 초기화
  → 방문 여부 배열
• 알고리즘 수행 (핵심 로직 실행)
  → 재귀, 큐, DP 점화식, 그리디 등 실제 탐색/계산
  →  pop - 가지치기 - 종료조건 - append  순서
  →  갱신 - 차수 감소 - 0 이면 큐 삽입  (위상 정렬)
      위처럼, 갱신 후 push 권장
• 결과 출력

 

- 기본 형태 :  visited = [False] * n  혹은  visited = set() 

• 그래프 탐색 시, 단순히 방문 여부만 기록 할 때 사용
• False = 아직 방문하지 않음
  → 방문시 True
  → 배열 값으로  -1  도 주로 사용
• 리스트 인덱스 접근 (해시 계산 없음, O(1)) + 불리언 값 확인 : 메모리 구조 단순 + 캐시 효율, 접근이 매우 빠름
  → 정수 인덱스 + 크기 고정 할당 + 빠른 인덱스 접근
  → 대규모 정수 노드 그래프에서 사용
• 멤버십 체크 (if x in visited 혹은 not in) 가 빠르고 직관적
  → in 연산 (O(1)) + 약간의 해시 연산 오버헤드 : 인덱스 접근보단 느림
  → 노드가 연속된 번호가 아님(문자열 가능) + 동적 확장 가능(크기 미리 알 필요 없음) + 불필요한 False 초기화 없음(공간 절약)
• set 기반 visited 에서는 접근 오류 없음 (리스트 기반은 있음)
  → visited를 인덱싱 접근(ex. visited[y][x]) 이 아닌,
      멤버십 테스트 ((x, y) in visited : True/False 결과) 와 추가 (visited.add((x, y)) : 중복 무시) 만 하기 때문
  → 따라서 KeyError / IndexError 발생하지 X, 초기값 필요 없음

 

- 부가 정보가 필요한 경우 (확장)

• 방문 여부 이상의 정보가 필요하다면 별도의 dict 혹은 리스트 를 함께 사용
• 필요하다면 2D 배열 형태로도 사용
• (예시) 트리/그래프 부모 노드, 거리, 시간스탬프 등 추가 메타데이터

visited = [False] * n
visited = set()
parent  = {}        # parent[node] = 이전 노드
parent  = [-1] * n  # -1 = 부모 없음
dist    = {}        # dist[node]   = 시작점으로부터 거리
dist    = [-1] * n  # -1 = 거리 비용(아직 방문 안함도 내포)

# 방문 직후 처리 예시
visited[nxt] = True
visited.add(nxt)
parent[nxt] = node
dist[nxt] = dist.get(node, 0) + 1
dist[nxt] = dist[node] + 1

 

 

- 거리 정의 (칸 수 vs 이동 횟수) + 시작점

• 무엇을 거리 (dist) 로 정의하느냐에 따라 초기값 (배열 생성시 X, 시작점 O) 이 달라짐

	정의	초기값	인접칸 업데이트	목표	대표 문제
칸 수 기준 (정점 수)	경로에 포함된 칸(정점)의 개수	1	dist[nx][ny] = dist[x][y] + 1	출발칸 포함 총 칸 수	게임 맵 최단거리, LIS, 경로 길이 DP 등
이동 횟수 기준 (간선 수)	실제 이동한 횟수(간선의 개수)	0	dist[nx][ny] = dist[x][y] + 1	이동한 칸 수(=한 칸당 1회)	그래프/BFS 일반형

※ 요약
- 자기 자신만 포함하는 경로 길이 = 1 (정점수 기준)
- 시작점에서 자기 자신까지는 이동이 없으므로 거리 = 0 (간선)

 

 

- 결과 수집 패턴

• 결과나 visited 처리에 사용됨
• 발견 수집형 (push 시 수집) : 큐/스택에 노드를 넣는 순간(=방문 표시와 동시에) 결과 리스트에 추가
  ( = 이웃을 발견해 방문 표시하는 순간 그 이웃을 수집하는 것)
  → 시작점은 루프 전에 따로 한 번 넣어둠 (초기화 필수)
  → 탐색 순서 = 결과 순서 (BFS는 레벨 순서, DFS는 스택 진입 순서)
  → 방문하는 순간에 해당 노드는 유효하다 가 확정 되는 경우 적합
  → 결과를 바로바로 쌓으므로 직관적
• pop 수집형 (pop 시 수집 / 후위 수집) : 큐/스택에서 꺼낼 때(=처리 완료 시점) 현재 노드를 수집 (결과 리스트에 추가)
  → 시작점은 루프에서 첫 pop 때 자연스럽게 들어감 (초기화 필요 X)
  → 후위 순서(post-order) 와 유사, 어떤 작업을 마친 뒤 결과를 모아야 하는 문제에서 적합
  → DFS에서는 위상정렬, Euler 경로, 여행경로 문제 등에 쓰임
  → BFS에서는 잘 쓰이지 않음 (∵ 레벨 순서가 필요할 때는 발견 시점이 자연스러움)

	DFS	BFS
발견 수집형	push 시 기록, 전형적인 연결요소 수집에 적합	enqueue 시 기록, 최단거리 계산/레벨 순서 수집에 사용
pop 수집형	후위 순서 필요할 때 사용 (위상정렬, Euler 경로 등)	효과상 큰 차이 없음 (발견=pop 순서)

 

 

4. 선택 기준 정리 

 

- 용도 관점

• 연결요소 분리 (컴포넌트 수집) 만 하면 됨 → BFS/DFS 모두 OK
• 최단거리/레벨 정보가 필요함 → BFS가 유리
• 깊이 우선으로 한 덩어리를 빠르게 털어가며 모으기 → DFS가 직관적

- 파이썬 구현 관점

• 재귀 DFS : 깊은 그래프 / 격자에서 RecursionError 위험 (Pyhon 기본 재귀 한도 ≈ 1000)
  → 반드시 반복(iterative) DFS(스택) 사용 (권장)
• 반복 DFS vs BFS : 스택/큐 둘다 O(1) 연산 (popleft, append/pop) 기반 (체감 차이 미미)
• 제한 크기가 작다면 스택/큐 메모리 차이 사실상 무시 가능

- 시간·공간 복잡도

• 시간 복잡도 : O(N+E) (그래프), 격자라면 O(N²)
  → N개의 노드(혹은 격자 칸)에서 BFS/DFS 모두 한 번씩 방문
• 공간 복잡도 :
  → 방문 체크 배열 : O(N) (혹은 O(N²) 격자)
  → 보조 자료구조 : 큐/스택 최대 O(N)까지 가능
  → 일반적으로 BFS/DFS 차이는 크지 않음