💻코딩테스트
[이코테_코딩테스트] DFS (Depth-First Search)
DFS (Depth-First Search)
- DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- DFS는 스택 자료구조(혹은 재귀 함수)를 이용
- 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
DFS 동작 예시
- [Step 0] 그래프 준비 (방문 기준 : 번호가 낮은 인접 노드부터라고 가정)
- 시작 노드 : 1
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fe92d5fee-2c7d-4ffd-a2c6-572cdc2de3d8%2FUntitled.png?table=block&id=5e3336b7-600c-4519-a478-34e0648faa45&cache=v2)
- [Step 1] 시작 노드인 ‘1’을 스택에 삽입 & 방문 처리
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F963cf1c1-afa0-4d97-9b20-89a8ca8f6a3d%2FUntitled.png?table=block&id=a2c0b005-e160-4b28-b3de-3eb875ddf04d&cache=v2)
- [Step 2] 스택의 최상단 노드인 ‘1’에 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’이 있다.
- 이 중 가장 작은 노드인 ‘2’를 스택에 넣고 방문 처리
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F305f1071-481f-49b5-957a-492862db37f0%2FUntitled.png?table=block&id=53e4e74d-f25a-475a-bba5-65a7e5d5fabe&cache=v2)
- [Step 3] 스택의 최상단 노드인 ‘2’에 방문하지 않은 인접 노드 ‘7’ 스택에 넣고 방문 처리
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F1c4f3c2a-63a5-4168-8629-c0cbb75a5a2c%2FUntitled.png?table=block&id=518caf4f-0e8a-41ee-b209-655382b1ae89&cache=v2)
- [Step 4] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드 ‘6’, ‘8’
- 이 중 가장 작은 노드인 ‘6’을 스택에 넣고 방문 처리
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F02ffda06-81d1-4adc-adab-08acde883551%2FUntitled.png?table=block&id=1a1049fe-ce7f-4c56-9300-9a0e03e1d57d&cache=v2)
- [Step 5] 스택의 최상단 노드 ‘6’에 방문하지 않은 인접 노드가 없다.
- 스택에서 ‘6’번 노드를 꺼낸다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fb0664d73-f256-4903-bdbe-d5eba6bd7b0a%2FUntitled.png?table=block&id=4938ce17-35dd-49e7-b8ed-7fb254395a8a&cache=v2)
- [Step 6] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드 ‘8’을 스택에 넣고 방문 처리
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fa231d6f8-66ee-446b-90f1-edcaaa957d02%2FUntitled.png?table=block&id=bd9a8feb-4677-4c82-b7c5-ed1d578e5e61&cache=v2)
- 위 과정을 반복하였을 때 전체 노드의 탐색 순서(스택에 들어간 순서)
- 탐색 순서 : 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5
DFS 소스코드 예제 (Python)
# DFS 함수 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트) graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트) visited = [False] * 9 # 정의된 DFS 함수 호출 dfs(graph, 1, visited)
이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 3. DFS & BFS” 영상을 보고 작성하였습니다.