탐색 알고리즘 - DFS/BFS

앞서 선형탐색/이분탐색을 공부하며 검색 알고리즘은 자료구조에 따라 배열 검색, 연결 리스트 검색, 이진검색트리 검색 등이 존재한다고 배웠다. 선형탐색/이분탐색은 배열 자료구조를 기반으로 하는 검색 알고리즘이었으며, 이 뒤에 배울 해쉬법은 배열과 연결리스트의 조합으로 해쉬 테이블이라는 자료구조를 만들어 사용하는 알고리즘이다.

그리고 이번에 공부한 DFS(깊이우선탐색)과 BFS(너비우선탐색)은 트리 구조를 기반으로 하는 검색 알고리즘이라고 볼 수 있다.

트리 구조

트리 구조에 대해서는 이후의 단원에서 더 깊이있게 공부를 하게 되겠지만, DFS와 BFS의 개념을 이해하기 위해 간단하게만 알아보자.

배열이 순서대로 나열된 자료구조라면, 트리는 데이터 사이의 계층 관계를 표현하는 자료구조다.

트리는 노드(node)와 가지(edge)로 이루어져 있으며 각 노드는 가지를 통해 다른 노드와 연결된다. 노드와 가지는 정점(vertex)과 간선으로 불리기도 하며, 두 노드가 가지로 연결된 경우를 ‘인접하다(adjacent)’고 표현한다.

가장 위쪽에 있는 노드를 루트(root)라고 부르며, 루트는 트리 하나에 1개만 존재한다. 그리고 가장 아래쪽에 있는 노드는 리프(leaf)라고 부르며, 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 의미로 단말 노드(terminal node) 또는 외부 노드(external node)라고도 부른다.

반대로 루트를 포함해 리프가 아닌 노드는 비단말 노드(non-terminal node) 혹은 내부 노드(internal node)라고 부른다.

트리의 표현방식

프로그래밍에서 트리구조는 크게 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) 2가지 방식으로 표현이 가능하다.

• 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현
• 인접 리스트: 리스트로 그래프의 연결 관계를 표현

인접행렬 (Adjacency Matrix)

2차원 배열에 각 노드가 연결된 형태를 기록하는 방식. 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성하는데, 실제 코드에서는 논리적으로 정답이 될 수 없는 큰 값 중에서 999999999 또는 987654321 등의 값으로 초기화를 시켜놓는다.

예)

INF = 999999999  # 무한(Infinity)의 비용이 될 상수 선언

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

인접리스트 (Adjacency List)

연결 리스트 자료구조를 이용해서 구현

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

효율성

인접행렬 방식은 모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 반면 인접리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.

하지만 인접 리스트 방식은 연결된 데이터를 하나씩 확인해야하기 때문에 인접 행렬에 비해 특정 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.

예를 들어 한 그래프에서 노드1과 노드7의 연결을 확인하고 싶을 때 인접행렬로는 graph[1][7]만 확인하면 되지만, 인접리스트는 연결된 모든 인접 노드를 순회해야한다.

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

깊이 우선 탐색은 트리에서 깊은 부분, 즉 리프에 도달하는 경로를 우선적으로 탐색하는 알고리즘이다. 리프에 도달할 때까지 원하는 값이 없으면 우선 위의 부모 노드로 돌아가고, 검색하지 않은 자식노드를 위주로 검색을 이어간다.

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

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

너비우선탐색 (BFS, Breadth-First Search)

너비 우선 탐색은 가장 멀리 있는 노드를 우선으로 탐색했던 DFS와 달리 인접한 가까운 노드들부터 탐색해가며 내려가는 알고리즘이다. 인접한 노드들부터 순차적으로 검색을 진행하기 때문에 BFS는 큐 자료구조를 이용해서 알고리즘을 작성한다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
3. 2번의 과정을 값을 찾았거나 더 이상 수행할 수 없을 때까지 반복한다.