#DFS

깊이 우선 탐색으로 경로 탐색, 트리 순회, 백트래킹 문제를 다룬다. 현재 4개의 풀이가 있다.

프로그래머스 리프 노드 수 최대화에서 깊이별 자식 수를 DFS로 선택하고, 분배 노드를 다음 단계로 넘기는 그리디 전략을 적용한다.

프로그래머스 '기차 선로'에서 DFS와 백트래킹으로 가능한 경로를 탐색한다. 선로 연결 방향과 3번 십자 선로의 처리 방식을 설명한다.

프로그래머스 여행경로에서 출발지별 도착지를 역순 정렬하고 스택 기반 DFS로 항공권을 모두 사용한다. 막다른 공항을 후위에 기록해 사전순 경로를 구성한다.

프로그래머스 바이러스 파이프에서 DFS로 파이프 배치 순서를 정하고 BFS로 같은 종류의 파이프를 따라 감염을 퍼뜨린다.

DFS 학습 가이드

필요한 주제만 펼쳐서 깊이 우선 탐색의 흐름, 방문 기록, 재귀와 백트래킹의 관계를 익힌다.

DFS 기본 개념

DFS(Depth-First Search)는 현재 노드에서 갈 수 있는 한 경로를 깊게 따라간 뒤, 더 갈 곳이 없으면 이전 분기점으로 돌아와 다른 경로를 탐색하는 알고리즘이다.

그래프 연결 요소, 트리 순회, 경로 존재 여부, 조합 탐색처럼 한 분기를 끝까지 확인해야 하는 문제에 자주 쓴다.

재귀 DFS와 명시적 스택

재귀 DFS에서는 함수 호출 스택이 현재 탐색 경로를 자동으로 저장한다. 재귀 깊이가 걱정되거나 상태를 직접 제어해야 하면 리스트를 명시적인 스택으로 쓸 수 있다.

def dfs(node):
    if visited[node]:
        return
    visited[node] = True

    for neighbor in graph[node]:
        dfs(neighbor)

방문 처리는 인접 노드를 재귀 호출하기 전에 해야 같은 노드가 여러 경로에서 반복 호출되는 것을 막을 수 있다.

방문 기록과 백트래킹

일반적인 그래프 DFS에서는 한 번 방문한 노드를 전체 탐색 동안 다시 방문하지 않는다. 반면 백트래킹에서는 현재 경로에서만 방문을 막고, 분기가 끝나면 상태를 복원해 다른 경로가 쓸 수 있게 한다.

DFS 문제 풀이 절차

인접 리스트를 사용하는 그래프에서 모든 노드와 간선을 한 번씩 처리하면 시간 복잡도는 `O(V + E)`다. 방문 배열과 호출 스택을 포함한 공간 복잡도는 `O(V)`다.

자주 하는 실수