DFS(깊이 우선 탐색) 완전 정복!

Depth First Search (깊이 우선 탐색)

한 번 시작하면 끝까지 파고드는 방식으로 문제를 푸는 탐색법이다.

1. DFS란?

*DFS (Depth First Search)**는 말 그대로 **‘깊이 우선 탐색’**이다.
간단히 말하면, 출발점에서 갈 수 있는 곳까지 최대한 깊이 들어갔다가,
더 이상 갈 곳이 없으면 뒤로 돌아와 다른 길로 가는 방식이다.

2. DFS의 핵심 특징

구분	설명
목적	모든 경우의 수를 탐색하기 위해 사용
구조	반복문 + 스택 자료구조
전략	갈 수 있는 길이 있다면 계속 전진! 없다면 한 칸 뒤로
구현	Stack 자료구조 사용 (list.pop() 사용)
대표 용도	지도 탐색, 모든 경우의 수 시도, 백트래킹 등

3. 지도 탐색뿐 아니라 모든 "경우의 수" 탐색

DFS는 단순히 지도만 탐색하는 게 아니다.
예를 들어:
- 모든 조합 찾기
- 모든 경로 탐색
- 백트래킹 문제 등등
- → 이런 문제들도 전부 DFS 개념으로 접근할 수 있다.

4. DFS 구조를 시각화해보자

graph_list = [
    [],         # 0번 도시는 없음 (사용하지 않음)
    [2, 3, 8],  # 1번 도시는 2, 3, 8번과 연결
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

예시: graph_list[3]의 연결 정보는?

출력: [1, 4, 5]
→ 3번 도시는 1, 4, 5번 도시와 연결되어 있다.

5. DFS 작동 원리 요약

1. 출발점(예: 1번 도시)을 방문할 곳 리스트에 넣는다.
2. 방문할 곳이 남아 있는 동안 계속 반복:
   1) 방문할 도시를 하나 꺼낸다 (Stack: 마지막에 들어간 게 먼저 나옴)
   2) 아직 방문하지 않았다면
      - 도장을 찍는다 (방문 리스트에 추가)
      - 연결된 도시들을 방문할 곳 리스트에 추가
3. 방문 순서를 기록하여 출력

6. DFS 코드 구현 (기본 버전)

def dfs(graph, start):
    need_visit = []   # 앞으로 방문할 도시들
    visited = []      # 이미 방문한 도시들

    need_visit.append(start)  # 출발 도시를 먼저 추가

    while need_visit:         # 방문할 곳이 남아있는 동안 반복
        node = need_visit.pop()  # 가장 마지막에 추가된 도시 방문 (Stack)

        if node not in visited:  # 처음 방문했다면
            visited.append(node)          # 방문 기록
            need_visit.extend(graph[node]) # 연결된 도시들 추가

return visited

이 함수가 하는 일 요약

어떤 도시부터 출발해서, 갈 수 있는 모든 도시를 DFS 방식으로 방문하고,
방문한 도시들의 순서를 차례대로 기록해서 돌려주는 함수다.

1. 함수 정의

def dfs(graph, start):

dfs라는 이름의 함수를 만든다.
(graph, start)는 이 함수에 2가지 정보를 넘긴다는 뜻이다.
1. graph: 도시들 간의 연결 정보가 담긴 자료 (예: 지도)
2. start: 탐색을 시작할 출발 도시 번호 (예: 1번 도시)

2. 방문해야 할 도시들과 이미 방문한 도시들을 저장할 리스트 만들기

need_visit = [] # 앞으로 방문할 도시들 
visited = [] # 이미 방문한 도시들

need_visit: 앞으로 방문해야 할 도시들을 담아두는 할 일 리스트다.
→ 나중에 여기에 있는 도시들을 하나씩 꺼내서 방문할 예정
visited: 이미 방문을 완료한 도시들의 목록이다.
→ 방문을 중복하지 않기 위해 기록함

3. 출발 도시를 가장 먼저 할 일 리스트에 넣기

need_visit.append(start)

출발 도시 번호(start)를 need_visit 리스트에 추가한다.
예: start = 1이라면 → need_visit = [1]이 됨
“출발 도시부터 가보자!”는 뜻

4. 방문할 도시가 남아있는 동안 계속 반복

while need_visit:

need_visit 리스트가 비어 있지 않은 동안 반복한다.
즉, 방문할 도시가 남아 있다면 계속 탐색을 진행하겠다는 뜻
몇 번 반복될지 모르기 때문에 while 반복문을 사용한다.

5. 방문할 도시를 하나 꺼낸다 (Stack 방식)

node = need_visit.pop()

pop() 함수는 리스트의 마지막 요소를 꺼내고 제거한다.
이 코드에서는 방문할 도시들 중 가장 마지막에 추가된 도시부터 방문한다.
이것이 바로 DFS의 핵심인 Stack 구조다.
→ 나중에 넣은 걸 먼저 꺼냄 (LIFO: Last-In-First-Out)

6. 처음 방문한 도시라면 방문 기록에 추가한다

if node not in visited:

꺼낸 도시(node)가 아직 방문한 적이 없는 도시인지 확인
만약 처음 방문한 도시라면 아래 코드들을 실행하고,
이미 갔던 곳이면 그냥 무시하고 넘어간다.

7. 방문 리스트에 추가 (도장 찍기)

visited.append(node)

방문한 도시를 visited 리스트에 추가한다.
이렇게 하면 나중에 누굴 방문했는지 순서대로 알 수 있음

8. 연결된 도시들(이웃들)을 방문할 리스트에 추가

need_visit.extend(graph[node])

현재 도시(node)에서 바로 연결된 도시들을 need_visit에 추가한다.
graph[node]는 해당 도시에서 직접 연결된 도시들의 목록이다.
extend()는 여러 개를 한꺼번에 추가할 때 사용한다.
- 예: [2, 3]을 추가하면 리스트가 [1, 2, 3]처럼 됨

9. 방문이 끝나면 결과 반환

return visited

DFS가 끝나고 나면, 방문한 도시들의 목록(visited)을 결과로 돌려준다.
예: [1, 8, 7, 6, 2, 3, 4, 5]

전체 흐름 요약 예제

graph_list = [
    [],          # 0번 도시는 없음
    [2, 3, 8],   # 1번 도시는 2, 3, 8번과 연결
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

실제 방문 순서:

DFS이기 때문에 Stack 구조로 깊이 우선 탐색됨 →
예: [1, 8, 7, 6, 2, 3, 4, 5]

정리

요소	설명
need_visit	앞으로 방문할 도시들 (할 일 목록)
visited	이미 방문한 도시들 (도장 찍은 목록)
while	방문할 도시가 남아있을 때까지 반복
pop()	Stack 방식으로 도시 꺼내기
if node not in visited	중복 방문 방지
extend(graph[node])	연결된 도시들 추가

7. 실행 결과

dfs(graph_list, 1)
# 출력 예시: [1, 8, 7, 6, 2, 3, 4, 5]

8. 정렬을 통한 방문 순서 제어

DFS는 기본적으로 Stack 구조를 사용하기 때문에,
연결된 도시들의 순서를 역순으로 넣어야 우리가 원하는 순서로 방문할 수 있다.

예: 1번 도시는 [2, 3, 8]과 연결되어 있음

→ Stack에 넣을 땐 [8, 3, 2] 순서로 넣어야

→ 나중에 꺼낼 때 [2, 3, 8] 순서대로 방문하게 된다.

정렬 적용한 DFS 코드

def dfs(graph, start):
    need_visit = []
    visited = []

    need_visit.append(start)

    while need_visit:
        node = need_visit.pop()

        if node not in visited:
            visited.append(node)

            # 연결된 도시들을 역순으로 넣기
            temp = graph[node]
            temp_reverse = list(reversed(temp))  # [2,3,8] -> [8,3,2]
            need_visit.extend(temp_reverse)

return visited

여기서 왜 reversed(temp)를 굳이 list()로 감싸는지 궁금함

temp_reverse = list(reversed(temp))

먼저 핵심만:

reversed(temp)는 리스트처럼 생겼지만 실제로는 리스트가 아니다.
그래서 list()로 감싸줘야 진짜 리스트가 된다.

차근차근 설명

1. reversed()의 정체

reversed(temp)는 리스트를 뒤집은 것처럼 보이는 "이터레이터(iterator)" 객체.
이터레이터는 반복 가능하지만, 리스트처럼 인덱스로 접근하거나 출력하면 바로 안 보이는 특수한 객체임.

예시:

temp = [2, 3, 8] 
print(reversed(temp)) 
# 출력해보면: 
# <list_reverseiterator object at 0x000001> 

print(list(reversed(temp))) 
# 진짜 리스트로 바꾼 뒤 출력 
# [8, 3, 2]

즉, reversed(temp) 자체는 우리가 보는 **[8, 3, 2]**처럼 생겼지만
사실은 그냥 반복 가능한 객체일 뿐임.

그래서 이걸 list()로 감싸줘야 실제로 다룰 수 있는 리스트가 된다.

2. 왜 꼭 리스트로 바꿔야 하냐면?

need_visit.extend(reversed(temp))

이렇게 써도 동작은 됨. 왜냐면 extend()는 이터러블(반복 가능한 것)이면 되기 때문.

하지만:

디버깅할 때, reversed(temp)는 바로 출력해서 확인할 수 없음
슬라이싱 같은 리스트 기능을 못 씀
명확하게 보여주고 싶을 때 list()로 감싸면 직관적으로 이해하기 쉬움

✅ 결론 요약

구분	설명
reversed(temp)	뒤집은 순서의 이터레이터(반복자) 객체
list(reversed(temp))	실제로 사용할 수 있는 리스트 형태로 변환

그래서 temp_reverse = list(reversed(temp))처럼 써주는 것이
가독성 좋고, 디버깅할 때도 편하고, 직관적으로 이해하기 쉬워서 사용함.

이터레이터가 뭔데?

✅ 1. 이터레이터(iterator)란?

이터레이터는 **"하나씩 꺼낼 수 있는 값들의 꾸러미"**
값을 한 번에 하나씩 꺼낼 수는 있지만, 전체를 한눈에 보이진 않음.

✅ 2. 리스트 vs 이터레이터 차이

리스트	이터레이터
[1, 2, 3]처럼 한눈에 보임	reversed([1, 2, 3])처럼 꺼내봐야 보임
인덱스로 접근 가능: a[0]	인덱스로 접근 ❌
반복 가능	반복 가능
메모리에 전체 값이 들어 있음	필요할 때 하나씩 꺼냄 (메모리 절약 가능)

✅ 3. 아주 쉬운 비유

리스트는?

과일 바구니를 한눈에 보는 것과 같음

[🍎, 🍌, 🍇]

전부 다 꺼내보지 않아도 안에 뭐가 있는지 한눈에 보임

이터레이터는?

택배 상자 안에 과일이 순서대로 들어 있는데,
하나씩 꺼내봐야 뭔지 알 수 있는 구조

next() → 🍎 next() → 🍌 next() → 🍇

전체 내용을 한 번에 보려면,
다 꺼내서 리스트처럼 만들어야 함 → list(이터레이터)로 감싸는 이유!

4. reversed()는 이터레이터!

예를 들어:

nums = [1, 2, 3] 
rev = reversed(nums)

rev는 그냥 이렇게 출력하면:

print(rev) 
# <list_reverseiterator object at 0x000001>

즉, 리스트처럼 보이지 않음!