그래프 탐색하기 위한 대표적인 알고리즘 DFS/BFS - DFS란?

 

그래프 탐색 알고리즘을 이해하기 위한 그래프 기본 구조

---

1. 그래프 (Graph)

그래프는 노드(Node)와 간선(Edge)으로 구성되며, 노드는 정점(Vertex)이라고도 부른다.

그래프 탐색은 하나의 노드를 시작으로 여러 노드를 방문하는 과정이다.

 

그래프는 주로 두 가지 방식으로 표현하는데, 코딩 테스트에서는 이 두 방식 모두 이해하고 활용하는 것이 중요하다.

 

1-1. 인접 행렬 (Adjacency Matrix)

• 그래프의 연결 관계를 2차원 배열로 나타내는 방식이다.
• 노드 간의 연결이 없으면 무한대(Inf)로 표현한다.
• 파이썬에서는 리스트로 2차원 배열을 구현한다.

인접 행렬 방식

# 인접 행렬 방식 예제
INF = 99999999 # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0,7,5],
    [7,0,INF],
    [5,INF,0]
]

print(graph)  

# 출력 [[0, 7, 5], [7, 0, 99999999], [5, 99999999, 0]]

 

 

1-2. 인접 리스트

인접 리스트 방식에서는 다음 그림처럼 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

인접 리스트는 '연결 리스트'라는 자료구조를 이용해 구현하는데, C++이나 자바 언어에서는 별도로 연결 리스트 기능을 위한 표준 라이브러리를 제공한다.

반면에 파이썬은 기본 자료형인 리스트 자료형이 append()와 메소드를 제공하므로, 전통적인 프로그래밍 언어에서의 배열과 연결 리스트의 기능을 모두 기본으로 제공한다. 

파이썬으로 인접 리스트를 이용해 그래프를 표현하고자 할 때에도 단순히 2차원 리스트를 이용하면 된다.

# 행이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드,거리)
graph[0].append((1,7))
graph[0].append((2,5))

# 노드 1에 연결된 노드 정보 저장
graph[1].append((0,7))

# 노드 2에 연결된 노드 정보 저장
graph[2].append((0,5))

print(graph)

# 출력: [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

 

1-3. 인접 행렬 vs 인접 리스트 

비교 기준	인접 행렬	인접 리스트
메모리 사용량	노드 개수 많을수록 메모리 낭비 발생	연결된 정보만 저장하여 메모리 효율적
특정 노드 간 연결 확인	O(1) (즉시 접근 가능)	O(N) (리스트를 순회하며 확인)
모든 인접 노드 순회	O(N)	O(연결된 노드 수)

• 인접 행렬은 특정 노드 간의 연결 여부를 빠르게 확인할 수 있지만, 메모리 낭비가 크다.
• 인접 리스트는 메모리를 효율적으로 사용하지만, 특정 노드 간 연결 여부를 확인하는 속도는 상대적으로 느리다.

---

 

2. DFS (Depth-First Search)

DFS는 깊이 우선 탐색 알고리즘으로, 한 경로로 가능한 깊이까지 탐색한 후, 다시 돌아가 다른 경로를 탐색하는 방식이다.

 

DFS 동작 과정

1. 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 
   * 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

* 방문 처리란, 이미 스택에 삽입된 노드가 다시 삽입되지 않도록 체크하는 것을 의미한다. 이를 통해 각 노드는 한 번씩만 처리된다.

 

DFS 예시 설명

아래 그래프에서 노드 1을 시작 노드로 DFS를 실행해보자.

깊이 우선 탐색이라는 이름에서부터 알 수 있듯이 단순하게 가장 깊숙이 위치하는 노드에 닿을 때 까지 탐색하면 된다. 

 

step1. 시작 노드인 '1'을 스택에 삽입하고 방문 처리를 한다. 

• 방문 처리된 노드: 회색
• 현재 처리하는 스택의 최상단 노드: 하늘색
• 스택: [1], 방문 노드: {1}

 

step2. 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '2', '3', '8'이 있다. 이 중에서 가장 작은 노드인 '2'를 스택에 넣고 방문 처리를 한다.

• 스택: [1,2], 방문 노드: {1,2}

 

step3. 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드 '7'이 있다. 따라서 '7'번 노드를 스택에 넣고 방문 처리를 한다.

• 스택: [1,2,7], 방문 노드: {1,2,7}

 

step4. 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '6'과 '8'이 있다. 이 중에서 가장 작은 노드인 '6'을 스택에 넣고 방문 처리를 한다.

• 스택: [1,2,7,6], 방문 노드: {1,2,7,6}

 

step5. 스택의 최상단 노드인 '6'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '6'번 노드를 꺼낸다.

• 스택: [1,2,7], 방문 노드: {1,2,7,6}

 

step6. 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '8'이 있다. 따라서 '8'번 노드를 스택에 넣고 방문 처리를 한다.

• 스택: [1,2,7,8], 방문 노드: {1,2,7,6,8}

step7. 스택의 최상단 노드인 '8'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '8'번 노드를 꺼낸다.

• 스택: [1,2,7], 방문 노드: {1,2,7,6,8}

 

step8. 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '7'번 노드를 꺼낸다.

• 스택: [1,2], 방문 노드: {1,2,7,6,8}

 

step9. 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '2'번 노드를 꺼낸다.

• 스택: [1], 방문 노드: {1,2,7,6,8}

 

step10. 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '3'을 스택에 넣고 방문 처리한다.

• 스택: [1,3], 방문 노드: {1,2,7,6,8,3}

 

step11. 스택의 최상단 노드인 '3'에 방문하지 않은 인접 노드 '4'와 '5'가 있다. 이 중에서 가장 작은 노드인 '4'를 스택에 넣고 방문 처리를 한다.

• 스택: [1,3,4], 방문 노드: {1,2,7,6,8,3,4}

 

step12. 스택의 최상단 노드인 '4'에 방문하지 않은 인접 노드가 '5'가 있다. 따라서 '5'번 노드를 스택에 넣고 방문 처리를 한다.

• 스택: [1,3,4,5], 방문 노드: {1,2,7,6,8,3,4,5}

 

step13. 남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 다음과 같다.

• 스택: [], 방문 노드: {1,2,7,6,8,3,4,5}

 

DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 또한, 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다.

# 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)

# 출력: 1 2 7 6 8 3 4 5

 

DFS의 특징

• 재귀적 구현으로 간단하게 작성 가능
• 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(V+E) (V: 노드 개수, E: 간선 개수)
• 스택을 활용하는 방식이므로 재귀 호출이 깊어질 경우 주의가 필요함

 

 

참고 자료

[1] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈, 한빛미디어)