[알고리즘 & 코테] Chapter 4. DFS/BFS

안녕하세요! 개굴코드입니다. 🐸
오늘은 지난번 살펴 보았던 구현 파트에 이어, 세 번째 챕터로 그래프 탐색 알고리즘에 해당하는 DFS/BFS 개념 및 구현에 대해 공부해보는 시간을 갖도록 하겠습니다!

자료구조 기초(Stack/Queue)

탐색은 많은 양의 데이터 중 원하는 데이터를 찾는 과정을 의미하고, 코딩 테스트에서는 그래프나 트리 안에서의 탐색 문제가 주로 출제된다고 합니다. 가장 대표적인 탐색 알고리즘이 바로 오늘 살펴볼 BFS와 DFS 인데, 이를 제대로 이해하기 위해서는 스택과 큐 자료 구조에 대한 이해가 선행되어야 한다고 해서, 알고리즘을 공부하기 이전 관련 자료 구조 이론들 먼저 보고 가도록 하겠습니다.

 

자료 구조는 데이터를 표현하고 관리하고 처리하기 위한 구조로, 대표적인 자료 구조로는 스택과 큐가 있습니다. 스택과 큐를 사용할 시에는 기본적인 삽입과 삭제, 오버플로(이미 꽉 찬 상태에서 삽입), 언더플로(비어 있는 상태에서 삭제)를 고려해야 합니다.

 

스택(Stack)

스택은 말 그대로 박스를 쌓는 구조와 비슷하며, First In Last Out(선입후출) 구조를 갖는 것이 가장 큰 특징입니다. 입구와 출구가 동일하기 때문에 처음 원소를 삽입하면 가장 안쪽에 쌓이고, 새로운 원소가 삽입될 때마다 그 위로 쌓입니다. 또 원소를 삭제할 시에는 가장 마지막에 삽입되었던 원소가 먼저 딸려 나옵니다. 아래 그림과 같습니다. 

 

 

이를 코드로 표현할 때는, 별도의 라이브러리를 사용할 필요 없이 기본 리스트와 append, pop 메소드를 사용하면 됩니다. append는 가장 후미에 원소를 삽입하고, pop 역시 가장 후미에서 원소를 빼기 때문입니다.

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

 

큐(Queue)

큐는 대기줄과 유사한 구조로, 스택과는 반대로 First In First Out(선입선출) 구조를 갖는 것이 가장 큰 특징입니다. 원소는 들어간 입구로 다시 빠져 나올 수 없기 때문에 일단 원소가 한번 삽입되면, 그 삽입된 순서대로 반대쪽 출구로 빠져 나옵니다. 아래 그림과 같습니다.

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용할 수 있습니다. deque를 사용하는 것이 리스트를 사용하는 것보다 삽입 삭제 속도 면에서 효율적이고, queue 라이브러리 보다 더 간단하다고 합니다.

from collections import deque

#큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

---

재귀

DFS/BFS 구현에 있어 재귀 함수에 대한 이해도 중요하다고 하여, 같이 살펴보겠습니다.

 

재귀 함수란, 자기 자신을 다시 호출하는 함수를 의미합니다. 재귀의 최대 깊이는 파이썬 인터프리터 상 정해져 있기 때문에 무한대로 재귀 호출을 진행할 수는 없습니다. 아래는 한계까지 계속 반복하는 재귀 함수 예시 입니다.

def recursive_function():
	print('재귀 함수를 호출합니다.')
	recursive function()
    
recursive function()

 

위의 예시처럼 별다른 조건이 없다면 함수가 무한 호출 될 수 있기 때문에, 재귀의 사용을 위해서는 재귀 함수의 끝, 종료 조건을 반드시 명시해야 합니다. 아래와 같이 if 문 등을 사용해서 해당 조건을 표현 할 수 있습니다.

def recursive_function(i):
	#100번째 출력했을 때 종료되도록 종료 조건 명시
	if i == 100:
	return
    	print(i, '번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다.')
	recursive_function(i + 1)
	print(i, '번째 재귀 함수를 종료합니다.')
    
recursive_function(1)

 

재귀 함수는 내부적으로 스택 자료구조와 동일하게 작동합니다. 함수를 계속 호출해 나갈 때 가장 마지막에 호출된 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문입니다. DFS가 스택 구조를 주로 활용해서 구현되기 때문에 재귀 함수의 사용을 반드시 염두에 두고 있어야 합니다.

---

그래프

마지막으로, DFS/BFS는 결국 그래프 관련 알고리즘이기 때문에 그래프에 대한 이해가 필수적입니다. 

 

그래프를 이해하기 위해서는 그래프의 구성을 간단히 알아야 하는데요, 그래프는 아래 그림과 같이 노드와 간선으로 이루어져 있습니다. 노드는 각각의 지점을 의미하고, 간선은 노드와 노드 사이를 이어주는 선이라고 봐주시면 됩니다. 또한 두 노드가 간선으로 연결되어 있다면 해당 두 노드를 서로 인접하다라고 표현할 수 있습니다.

 

그래프는 2가지 방식으로 코딩할 수 있는데, 인접 행렬과 인접 리스트가 그 두 가지 방식에 해당합니다. 먼저 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식입니다. 아래 왼쪽 그림과 같이 그래프가 있다면, 노드 간 간선 비용을 오른쪽 2차원 배열처럼 표현할 수 있습니다. 이 때 핵심은 실제로 연결되어 있는 노드는 실제 비용으로 표기하고, 나머지는 무한대 비용을 적용하는 것으로 표현하는 것입니다. 2차원 리스트의 인덱스를 통해 [0][0], [0][1]에 비용 값을 넣을 수 있습니다.

INF = 999999999 # 무한의 비용 선언

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

 

두 번째로 인접 리스트에서는 아래 그림처럼 각 노드마다 연결된 모든 노드에 대한 정보를 이어붙이는 방식으로 표현합니다. 연결 리스트를 사용하여 구현할 수 있는데, 파이썬에서는 별도의 연결 리스트가 없기 때문에 그냥 일반 2차원 리스트에서 각 노드에 연결된 노드와 그 거리를 삽입하여 표현합니다.

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

 

인접 행렬 방식은 모든 정보를 저장하기 때문에 메모리 사용량은 많지만, 특정 관계를 쉽게 슬라이싱 할 수 있다는 장점이 있고, 반대로 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리 사용량은 적지만, 노드간 연결 여부를 확인 하기 위해서는 연결된 데이터를 하나씩 확인해야 하기 때문에 그 속도가 느리다는 단점이 있습니다.

---

DFS

서론이 조금 길었는데요. 본격적으로 알고리즘 자체에 대해 살펴보도록 하겠습니다.

 

DFS(Depth-First-Search)는 깊이 우선 탐색으로 부르며, 그래프의 가장 깊은 부분부터 우선적으로 탐색을 진행하는 알고리즘 입니다. 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 방식에 해당하며, 구체적인 동작 과정은 다음과 같습니다. 

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

-> 이 때 방문 처리는 이미 스택에 삽입되어 한 번 처리된 노드를 다시 처리하지 않게끔 일종의 마킹을 해두는 것입니다.

 

해당 그래프 예제를 토대로, DFS 과정을 한번 살펴 보겠습니다. 시작 노드는 1로 설정한 것입니다.

 

1) 시작 노드인 1을 스택에 삽입하고, 방문 처리를 합니다. (1)

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

3) 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드 '7'이 있고, 따라서 '7번 노드를 스택에 넣고 방문처리를 합니다. (1,2,7)

4) 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '6'과 '8'이 있습니다. 이 중에서 가장 작은 노드인 '6'을 스택에 넣고 방문 처리를 합니다. (1,2,7,6)

5) 스택의 최상단 노드인 '6'에 방문하지 않은 인접 노드가 없습니다. 따라서 스택에서 '6'번노드를 꺼냅니다. (1,2,7)

6) 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '8'이 있습니다. 따라서 '8'번 노드를 스택에 넣고 방문처리를 합니다. (1,2,7,8)

7) 스택의 최상단 노드인 '8'에 방문하지 않은 인접 노드가 없습니다. 따라서 스택에서 '8'번 노드를 꺼냅니다. (1,2,7)

8) 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '7'번 노드를 꺼냅니다. (1,2)

9) 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드가 없습니다. 따라서 스택에서 '2'번 노드를 꺼냅니다. (1)

10) 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '3'을 스택에 넣고 방문 처리합니다. (1,2,3)

11) 스택의 최상단 노드인 '3'에 방문하지 않은 인접 노드 '4'와 '5'가 있습니다. 이 중에서 가장 작은 노드인 '4'를 스택에 넣고 방문 처리를 합니다. (1,2,3,4)

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

 

이렇게 모든 단계를 거치면, 1-2-7-6-8-3-4-5 순으로 탐색하는 것이 됩니다.

 

DFS는 위에서 말했듯 재귀와 스택 자료구조를 사용하면 보다 손쉽게 구현이 가능합니다. 시간 복잡도는 O(N)이고, 아래는 위의 그래프 예제에 대한 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)

---

BFS

다음으로 BFS(Breadth First Search)는 너비 우선 탐색 알고리즘으로 불립니다. DFS가 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다면, BFS는 그 반대로 가장 가까운 노드부터 탐색하는 알고리즘입니다. 

 

BFS 구현에는 FIFO 방식의 큐 자료구조를 사용하는 것이 정석으로 여겨지고 있습니다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 되기 때문입니다. 정확히는 다음과 같은 방식으로 작동합니다.

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

 

위 DFS에서의 그래프 예제를 토대로, BFS 과정을 한번 살펴 보겠습니다. 시작 노드는 1로 동일하게 설정하고, 인접 노드가 여러개 있을 때는 마찬가지로 숫자가 작은 노드부터 먼저 큐에 삽입합니다.

 

 

1) 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 합니다. (1)

2) 큐에서 노드 '1'을 꺼내고 방문하지 않은 인접 노드 '2', '3', '8'을 모두 큐에 삽입하고 방문 처리를 합니다. 숫자가 낮은 2부터 들어갑니다. (2,3,8)

3) 큐에서 노드 '2'을 꺼내고 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문 처리를 합니다. (3,8,7)

4) 큐에서 노드 '3'을 꺼내고 방문하지 않은 인접 노드 '4','5'를 모두 큐에 삽입하고 방문 처리를 합니다. (8,7,4,5)

5) 큐에서 노드 '8'을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시합니다. (7,4,5)

6) 큐에서 노드 '7'을 꺼내고 방문하지 않은 인접 노드 '6'을 큐에 삽입하고 방문 처리를 합니다. (4,5,6)

7) 남아 있는 노드에 미방문 인접 노드가 없고, 따라서 모든 노드를 차례대로 꺼낸 후 종료합니다. ()

 

이렇게 모든 단계를 거치면, 1-2-3-8-7-4-5-6 순으로 탐색하는 것이 됩니다.

 

BFS는 위에서 말했듯 deque 라이브러리를 사용하면 보다 손쉽게 구현이 가능합니다. 시간 복잡도는 O(N)이고, 실제 수행 시간 측면에서 DFS보다 더 우수합니다. 아래는 위의 그래프 예제에 대한 DFS 탐색 로직을 파이썬으로 구현한 것입니다.

from collections import deque

#BFS 메서드 정의
def bfs(graph, start, visited):
    #큐(Queue) 구현을 위해 deque 라이브러리 사용
    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
                
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
	[ ],
	[2, 3, 8],
	[1, 7],
	[1, 4, 5],
	[3, 5],
	[3, 4],
	[7],
	[2, 6, 8],
	[1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

#정의된 BFS 함수 호출
bfs(graph, 1, visited)

---

최종 정리해보면, 다음 표와 같이 DFS와 BFS를 나타낼 수 있습니다.

 

또한, 위의 전형적인 무방향 그래프에서만 BFS와 DFS를 적용할 수 있는 것이 아니고, 앞서 구현 문제에서 몇번 보았던 2차원 배열, 좌표계 등을 주로 그래프 형태로 생각하고 이러한 탐색 알고리즘 등을 적용하여 문제 풀이를 할 수 있습니다. 물론 주어진 상황을 그래프 구조로 표현하는 데에 추가 코드가 필요하겠지만 말입니다.

---

오늘은 자연스러운 흐름을 위해 많은 개념들을 한꺼번에 몰아서 살펴봤는데, 교재의 그래프 탐색 대표 예제 및 백준 관련 문제 풀이는 다음 포스팅들에서 차차 이어서 진행해보도록 하겠습니다. 그럼 다음 포스팅으로 돌아오겠습니다! 🐸