[알고리즘] DFS(Depth-First Search) 이해하기

DFS 란 무엇인가?

 

앞에 복잡한 미로가 있다고 상상해본다. 출구를 찾기 위해 어떻게 할것 인가.. 아마 많은 사람들이 일단 한 갈래 길을 선택해서 막다른 길이 나올때 까지 쭉 가본다고 생각한다. 만약 막다른 길을 만나면, 직전 갈림길로 돌아와서 아직 가보지 않은 길을 선택해 다시 끝까지 가보겠죠?

 

 

이게 DFS 이다.

 

왜 DFS를 사용할까?

 

⏰ 시간 복잡도

- 인접 행렬: 모든 노드(V) 간의 연결을 확인해야 할 수 있어 O(V²) 시간이 소요됩니다.

- 인접 리스트: 실제 연결된 노드(V)와 간선(E)만 탐색하므로 O(V+E) 시간이 걸려 보통 더 효율적입니다.

(V: 노드 개수, E: 간선 개수)

 

👍 장점

- 현재 경로만 기억하므로 메모리 사용량이 적습니다.

- 너비 우선 탐색(BFS)에 비해 구현이 상대적으로 간단할 수 있습니다 (특히 재귀 사용 시).

- 목표 지점이 깊은 곳에 있다면 해를 더 빨리 찾을 수 있습니다.

 

👎 단점

- 정답이 없는 경로를 깊게 탐색하며 시간을 허비할 수 있습니다.

- 찾은 해답이 최단 경로가 아닐 수 있습니다. (목표 도달 즉시 탐색을 종료할 수 있으므로)

 

 

---

 

간단한 DFS 백준 문제를 예시로 풀어보자!

 

https://www.acmicpc.net/problem/2606

 

 

 

 

n=int(input()) # 컴퓨터 개수
v=int(input()) # 연결선 개수

graph = [[] for i in range(n+1)] # 그래프 초기화
print(graph)

visited=[0]*(n+1) # 방문한 컴퓨터인지 표시
for i in range(v): # 그래프 생성
    a,b=map(int,input().split())
    graph[a]+=[b] # a에 b 연결
    graph[b]+=[a] # b에 a 연결 -> 양방향
    
def dfs(v):
    visited[v]=1
    for nx in graph[v]:
        if visited[nx]==0:
            dfs(nx)
dfs(1)
print(sum(visited)-1)

 

입력 및 그래프 생성.

n에는 컴퓨터 개수를 입력받고, v에는 연결선의 개수를 입력받습니다. 

 

graph는 n+1개만큼 빈 리스트를 생성합니다. n+1개인 이유는 1번 컴퓨터를 1번 인덱스를 쓰기 위해, 1개 더 추가한 것입니다. visited는 n+1 길이의 0으로 이루어진 리스트로, 해당 컴퓨터를 방문했는지 표시하는 리스트입니다.(0: 미방문, 1: 방문)

 

연결선 개수만큼 for문을 반복하며 연결된 컴퓨터 번호를 각각 a, b로 입력받습니다. graph에서 a컴퓨터에 b를 넣고, b컴퓨터에 a를 넣음으로써 쌍방 연결돼있음을 표시합니다.

 

 

---

🔸 Step 1: dfs(1)

• 방문 표시: visited[1] = 1
• graph[1] = [2, 5]
• 첫 번째 인접 노드인 2로 진입

🔸 Step 2: dfs(2)

• 방문 표시: visited[2] = 1
• graph[2] = [1, 3, 5]
• 1은 이미 방문했으므로 skip
• 다음 인접 노드 3으로 진입

🔸 Step 3: dfs(3)

• 방문 표시: visited[3] = 1
• graph[3] = [2]
• 2는 이미 방문했으므로 종료
• 돌아감 → Back to dfs(2)

🔸 Back to Step 2

• 남은 인접 노드 5 확인 → 아직 방문 안 함
• dfs(5) 호출

🔸 Step 4: dfs(5)

• 방문 표시: visited[5] = 1
• graph[5] = [1, 2, 6]
• 1, 2는 이미 방문했음
• 6으로 진입

🔸 Step 5: dfs(6)

• 방문 표시: visited[6] = 1
• graph[6] = [5] → 이미 방문한 노드
• 종료 → Back to dfs(5), dfs(2), dfs(1)

---

🔚 DFS 종료

최종적으로 방문된 노드: 1, 2, 3, 5, 6
→ 감염된 컴퓨터 수: 5 - 1 = 4대

 

 

끝.