[자료구조] DFS & BFS

0. DFS, DFS 학습 전 알아야 할 것 

인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식

파이썬에서도 2차원 리스트로 구현한다. 연결이 되어 있지 않은 경우에는 논리적으로 정답이 될 수 없는 큰 값 중 999999999 등의 값으로 초기화해서 사용한다.

 

INF = 999999999

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

 

인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식, 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

인접 리스트는 연결 리스트를 사용하면 되는데, 연결 리스트의 경우 파이썬은 기본 자료형인 리스트 자료형이 append 등 메소드를 제공하기 때문에 단순히 2차원 리스트를 사용해도 된다. 

 

graph = [[] for _ in range(3)]

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

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

 

- 메모리 측면에서 보면 인접 행렬 방식은 모든 관계를 저장하므로 메모리가 불필요하게 낭비되고, 인접 리스트는 연결된 정보만을 저장하기 때문에 효율적으로 사용한다.

반면 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.

 

1. DFS (Depth-First Search) 깊이 우선 탐색

: 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.

스택 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다.

 

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

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

3) 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.

 

깊이 우선 탐색은 스택 자료구조에 기초한다는 점에서 구현이 간단하고 재귀함수를 이용했을 때 유리하다.

데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다는 특징이 있다. 

 

def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
    visited[v] = True
    print(v,end=' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
graph = [
 [],
 [2,3,8],
 [1,7],
 [1,4,5],
 [3,5],
 [3,4],
 [7],
 [2,6,8],
 [1,7]
]

visited = [False] * 9
dfs(graph, 1, visited)

 

2. BFS (Breath First Search) 너비 우선 탐색

가까운 노드부터 탐색하는 알고리즘이다. BFS는 큐 자료구조를 많이 사용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게되어, 가까운 노드부터 탐색을 진행하게된다. 

동작방식은 다음과 같다.

 

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

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

3) 2의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

deqeue 라이브러리를 사용하는 것이 좋고 탐색을 수행함에 있어서 O(N) 시간이 소요된다. 일반적으로 수행시간은 DFS보다 좋다.

 

from collections import deque

def dfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    
    while queue:
    	v = queue.popleft()
        print(v,end="")
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
             queue.append(i)
             visited[i] = True
             
graph = [
	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
	[7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9
bfs(graph, 1, visited)
    
]

 

코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각하면 풀이 방법을 조금 더 쉽게 떠올릴 수 있다. 

 

참고) 이것이 코딩 테스트다.