[PS] DFS 개념 및 파이썬 코드

그래프는 노드(Node) 와 간선(Edge)로 표현되며 노드를 정점(Vertex) 라고 말한다.

 

그래프 탐색은 하나의 노드를 시작으로 모든 노드를 방문하는 것을 말하고, 두 노드가 간선으로 연결 되어 있다면, 두 노드는 인접(Adjacent)하다고 한다.

---

깊이 우선 탐색(DFS)

깊이 우선 탐색은 Depth First Search 로 루트 노드에서 시작하여 다음 branch 로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법이다.

 

DFS 에서 노드 탐색 순서는 아래와 같다.

DFS

---

특징

- 모든 노드를 탐색해야 할 때 활용하기 좋은 방식이다.

- BFS(깊이 우선 탐색) 보다 간단하지만 속도가 느리다.

---

구현 알고리즘

1. 루트노드에서 탐색을 시작한다.

2. 현재 노드에서 인접하고 방문하지 않은 노드를 방문한다.

3. 현재 노드에 인접하거나 방문하지 않은 노드가 없을 경우 갈림길로 돌아와 다른 방향의 노드를 방문한다.

 

순서는 아래와 같다.

(출처 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html)

DFS 알고리즘

---

그래프 구현방식

코드로 이를 구현 하기 위헤서는 2가지 방법이 있다.

1. 인접 행렬

2. 인접 리스트

 

위와 같은 그래프를 인접행렬과 인접 리스트로 표현 해보자.

인접행렬

인접행렬은 2차원 배열에 각 노드가 연결된 형태를 boolean 값(true, false)을 이용하여 기록하는 방식이다.

인접행렬

인접 리스트

인접리스트 방식은 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장하는 방식이다.

파이썬 에서는 기본 자료형은 리스트 자료형에 append()를 통해서 구현 할 수 있다.

인접 리스트

---

구현 코드

인접 행렬

def dfs(node):
    # 현재 노드를 방문 처리
    is_visited[node] = True
    visit_arr.append(node)  # 방문한 노드 리스트에 추가

    # 인접 노드 탐색
    for i in range(1, node_num + 1):  # 노드 번호는 1부터 시작한다고 가정
        if graph[node][i] == 1 and not is_visited[i]:  # 인접 노드이고 방문하지 않았으면
            dfs(i)  # 재귀 호출로 다음 노드 방문

 

인접행렬 배열을 graph, 방문여부 배열을 is_visited, 방문한 노드를 순서대로 저장하는 배열을 visit_arr 이라고 하면 위와 같이 코드를 작성 할 수 있고 시간 복잡도는 O(N^2) 가 된다.

# 예제 데이터 초기화
node_num = 5  # 노드 개수 (예시)
graph = [      # 인접 행렬 (예시)
    [0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0, 0],
    [0, 1, 0, 0, 1, 0],
    [0, 1, 0, 0, 1, 1],
    [0, 0, 1, 1, 0, 1],
    [0, 0, 0, 1, 1, 0]
]
is_visited = [False] * (node_num + 1)  # 방문 여부를 저장하는 리스트
visit_arr = []                         # 방문 순서를 저장하는 리스트

# DFS 실행
dfs(1)  # 시작 노드는 예시로 '1'
print("방문 순서:", visit_arr)

 

인접행렬이 주어졌을때 예시는 위와 같다.

 

인접 리스트

def dfs(node):
    is_visited[node] = True  # 노드 방문 여부를 True로 저장
    visit_arr.append(node)   # 방문한 노드를 순서대로 저장하는 리스트에 해당 노드 추가
    
    for adj_node in graph[node]:  # 현재 노드의 인접 노드들을 순회
        if not DFS_is_visited[adj_node]:  # 방문되지 않은 인접 노드라면
            dfs(adj_node)  # 재귀적으로 DFS 수행

인접 행렬과 똑같이 인접리스트 배열을 graph, 방문여부 배열을 is_visited, 방문한 노드를 순서대로 저장하는 배열을 visit_arr 이라고 하면 위와 같이 구현할 수 있고 시간 복잡도는 O(N + E) 가 된다.

 

# 그래프 초기화 (예시)
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4, 5],
    4: [2, 3],
    5: [3]
}

# 방문 여부를 저장할 딕셔너리 초기화
DFS_is_visited = {node: False for node in graph}

# 방문 순서를 저장할 리스트 초기화
DFS_visit_arr = []

# DFS 실행 (시작 노드: 1)
dfs(1)

print("DFS 방문 순서:", DFS_visit_arr)

 

예시는 위와 같다.

---

요즘 알고리즘 문제 풀이에 재미가 들려서 solved.ac 문제를 풀고 있는데 정리를 한번 해두면 좋을것 같아서 글을 적었다.

DFS는 그래프 탐색 문제의 기본이 되는 알고리즘 중 하나여서 알아둘 필요가 있다.