[코딩공부] DFS/BFS (2) - DFS/BFS

이번 포스팅에서는 지난 포스팅에 이어서 DFS/BFS 알고리즘을 다루어 보도록 하겠습니다. 우선 DFS를 다루고자 하는데요.

DFS의 풀네임은 Depth-First Search입니다. 즉 깊이 우선 탐색인데요 그래프에서 가장 깊은 곳을 우선으로 탐색하는 알고리즘입니다. 이 책에서는 그래프에서 대해서 먼저 설명하고 있는데요 그래프는 노드(node) 와 간선(Edge)로 구성되어 있습니다. 여기서 노드는 정점이라고 하는데 우리가 흔힌 말하는 그래프 탐색은 그래프의 어떤 한 지점 즉 노드를 시작으로 다수의 노드를 방문하는 것을 의미합니다. 여기서 간선으로 연결되어 있는 노드를 두 노드가 인접하다고 표현하게 됩니다.

 

그래프를 표현하는 방식으로 인접 행렬(Adjacency Matrix) 그리고 인접 리스트(Adjacency List) 두가지가 있습니다. 

 

#인접 행렬 방식 예제

INF = 9999999999999999  # 무한의 비용을 선언 / 즉 연결 되어 있지 않음을 의미

graph = [ 
		[0,7,5], # 0은 자신을 의미 # INF는 연결되어 있지 않음을 의미 / 나머지 숫자는 가는데 필요한 비용
        [7,0,INF],
        [5,INF,0]
]

# 인접 리스트(Adjacency List) 는 모든 노드에 연결되어 있는 정보를 저장

# 3개의 노드가 있다고 정의
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))

 

두가지 방식을 비교하면, 그래프의 크기가 커질 수록 인접행렬 방식은 메모리 관점에서 비효율 적이다 연결되어 있지 않은 정보도 저장되기 때문이다. 하지만 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도에서는 인접 리스트 방식이 느리다. 

 

그렇다면 DFS의 동작 방식은 무엇일까? DFS는 스택 자료 구조를 이용하며 구체적인 동작과정은 다음과 같다.

 

1) 탐색 시작 노드를 스택에 삽입하고 방문처리한다. 

 

2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 

 

3) 2번의 과정을 통해서 수행할 수 없을 때까지 반복한다.

 

예제는 아래와 같다. 

 

graph = [
	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7],
    ]

visited =[False] * 9

def dfs(g, node, visit):
    visit[node] = True
    print(str(node) + ' ')
    for v in g[node]:
        if not visit[v]:
            dfs(g, v, visit)

dfs(graph, 1, visited)

 

그렇다면 다음은 BFS(Breadth First Search) 에 대해서 다루어보도록 하겠습니다. 한국어로 표현 하면 너비 우선 탐색입니다. 즉 최대한 멀리 있는 노드부터 탐색하는 DFS와는 달리 선입선출 큐 자료구조를 활용하여 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 된다. 

 

동작 방식은 다음과 같다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

 

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 

 

3. 2번의 과정을 반복할 수 없을 때까지 반복한다. 

 

* 일반적으로 DFS 보다 수행 시간이 좋은 편이라는 점을 기억하여야 한다. 

 

from collections import deque
graph = [
	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7],
    ]

visited =[False] * 9

def bfs(g, node, visit):
    queue = deque([node])
    visit[node] = True
    while queue:
        v = queue.popleft()
        print(v)
        for i in g[v]:
            if not visit[i]:
                queue.append(i)
                visit[i] = True

bfs(graph, 1, visited)