알고리즘 기초 - 깊이 우선 탐색(DFS)

---

DFS란 무엇일까?

---

DFS는 그래프 탐색 알고리즘 중 하나로, 한 방향으로 끝까지 파고 들어간 뒤 더 이상 진행할 수 없을 때 다시 돌아와 다른 경로를 탐색하는 방식이에요. 트리 탐색이나 미로 문제 같은 곳에서 자주 등장합니다.

 

👉 쉽게 말하면, "갈 수 있는 길이 있으면 계속 들어가고, 막히면 돌아와서 다른 길을 찾는 방법"이에요.

 

 

동작 방식

DFS의 핵심 아이디어는 스택(Stack) 구조입니다.
재귀 함수를 사용하면 내부적으로 스택이 사용되기 때문에 구현이 간단해집니다.

동작 순서를 정리하면:

1. 시작 노드에서 출발
2. 아직 방문하지 않은 인접 노드를 하나 골라 방문
3. 더 이상 방문할 노드가 없으면 이전 노드로 돌아감 (백트래킹)
4. 모든 노드를 방문할 때까지 반복

 

---

DFS의 특징

---

 

장점

• 구현이 간단하다 (특히 재귀 활용 시)
• 그래프의 모든 경로를 확인할 수 있다
• 백트래킹과 조합 문제에 유용하다

단점

• 경로가 길어지면 스택 오버플로우 위험(재귀 제한)
• 최단 경로 탐색에는 적합하지 않다 (BFS가 더 적합)

---

구현 방법

---

 def dfs_stack(graph, start):
    visited = []            # 방문한 노드를 기록할 리스트
    stack = [start]         # 탐색을 시작할 스택 (시작 노드 넣기)

    while stack:            # 스택이 빌 때까지 반복
        node = stack.pop()  # 스택의 맨 위 노드를 꺼냄
        if node not in visited:   # 아직 방문하지 않았다면
            visited.append(node)  # 방문 처리
            # 인접 노드를 스택에 추가 (순서를 맞추기 위해 reversed)
            stack.extend(reversed(graph[node]))
    return visited          # 방문한 노드 순서를 반환


graph = {
    1: [2, 3, 8],
    2: [1, 7],
    3: [1, 4, 5],
    4: [3, 5],
    5: [3, 4],
    6: [7],
    7: [2, 6, 8],
    8: [1, 7]
}

print(dfs_stack(graph, 1))

코드 동작 흐름

1. 초기화
   • visited는 방문한 노드를 저장하는 리스트입니다.
   • stack에는 탐색할 노드를 넣는데, 시작 노드 start부터 넣습니다.
2. 반복 탐색
   • 스택이 빌 때까지 while문을 돌립니다.
   • stack.pop()으로 가장 최근에 넣은 노드를 꺼내옵니다 (LIFO, 후입선출).
3. 방문 체크
   • 만약 해당 노드를 visited에 아직 넣지 않았다면, 방문 리스트에 추가합니다.
4. 인접 노드 추가
   • 현재 노드와 연결된 인접 노드를 stack에 넣습니다.
   • 이때 reversed를 사용하는 이유는, 스택 구조상 뒤에 넣은 게 먼저 나오므로 방문 순서를 사람이 보기 좋은 오름차순으로 맞추기 위함입니다.
5. 종료
   • 모든 노드를 탐색하면 visited를 반환합니다.

---

마무리

---

DFS는 "끝까지 가본다"는 단순한 아이디어지만, 많은 문제 해결의 기본이 되는 탐색 기법이에요.
특히 재귀 호출과 스택 구조를 함께 이해하면 BFS와 비교하면서 문제 해결력이 훨씬 넓어집니다.