이코테 Ch.3 DFS/BFS (1)

자료구조 기초

자료구조의 기초에 대해 공부해야하는 이유는, 알고리즘들에 자료구조의 개념이 자연스럽게 녹아있기 때문이다.

대표적인 자료구조에는 스택과 큐가 있다.

스택

스택은 바닥부터 상자를 쌓는 경우에 비유할 수 있다. 맨 아래에 있는 박스를 꺼내기 위해서는 우선 위에 쌓인 박스들부터 꺼내야한다.

더 자세하게 말하자면, 맨 아래 깔린 박스는 내가 가장 먼처 가져다 놓은 박스이고 내가 이 박스를 꺼내기 위해서는 가장 마지막에 쌓은 박스를 먼저 꺼내야한다.

이런 구조를 선입 후출 구조라고 하는데, 스택이 바로 여기에 해당한다. 스택도 가장 먼저 넣은 데이터가 제일 마지막에 꺼내지는 구조기 때문이다.

코드로 예시를 들어보면,

stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack)
print(stack[::-1])

"""
result
[5, 2, 3, 1]
[1, 3, 2, 5]
"""

파이썬에서 스택 자료구조를 사용할 때는 별도의 라이브러리를 사용할 필요가 없다. 이는 기본적으로 파이썬의 리스트가 전형적인 스택구조로 작동하기 때문이다. 스택구조를 사용해야한다면 리스트를 만들고 append와 pop으로 데이터를 넣고 빼기만 하면 된다.

큐

큐는 대기줄에 비유할 수 있다. 새치기가 없다면, 가장 먼저 줄선 사람이 먼저 들어가는 구조라는 것이다. 이러한 구조는 선입 선출의 구조라고한다.

큐는 앞선 스택 자료구조와는 달리, 파이썬 모듈을 사용하여 표현한다.

코드로 표현하면,

from collections import deque

queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)
queue.reverse()
print(queue)
print(list(queue))

collections 모듈의 deque 라이브러리는 스택과 큐의 장점을 채택한 deque 자료구조를 만들어주는 데, queue라이브러리를 쓰는 것보다 더 간단하게 큐 자료구조를 만들 수 있다.

참고로 deque라이브러리를 사용해서 큐를 만들면 deque객체에 담기게 된다. 만약 deque 객체를 리스트 자료형으로 변경하고 싶다면 list() 메서드를 사용하면 된다.

재귀 함수

자료구조개념을 사용하는 대표적인 알고리즘 유형으로는 탐색 알고리즘이 있다. 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.

프로그래밍에서는 주로 그래프, 트리 등의 자료 구조 안에서 탐색이 이루어지는데, 이와 직접적으로 연관된 탐색 문제가 DFS와 BFS다.

그리고 DFS와 BFS를 구현하기 위해서 먼저 알아야하는 개념이 재귀함수이다.

재귀함수는 자기 자신을 다시 호출하는 함수를 의미한다. 재귀함수는 종료조건이 중요한데, 종료조건이 없으면 자기자신을 무한히 호출하게 되기 때문이다.

기본적으로 재귀함수의 수행은 스택 자료구조형태이다. 가장 마지지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 이러한 특성으로 인해 스택자료구조를 갖는 알고리즘은 상당수 재귀함수를 이용하면 간편하게 해결이 가능하다.

재귀함수의 대표적인 예시인 팩토리얼 예제를 보면,

def factorial_recursive(n):
	if n <= 1: # 종료조건 : n이 1이하면 1 리턴
		return 1
	# n! = n * (n-1)!
	return n * factorial_recursive(n-1)

print(factorial_recursive(5))

재귀함수는 결국 n의 범위에 따라 작성된 점화식이라고 보면 이해가 쉽다.

• n ≤ 1 : factorial(n) = 1
• n > 1 : factorial(n) = n * factorial(n-1)

탐색 알고리즘 DFS/BFS

탐색 알고리즘은 기본적으로 그래프와 연관이 깊다. 따라서 DFS든 BFS든 그래프와 연관지어서 이해하면 좀 더 쉽게 문제해결이 가능하다.

따라서 어느정도 그래프에 대한 기본 개념 학습이 선행되어야 한다.

그래프는 기본적으로 노드와 간선(Edge)으로 구분된다. 노드는 사실 좀 익숙하게 느껴지는데 우리가 클러스터링을 진행할 때, 클러스터 내의 컴퓨터를 노드라고 부르는 것과 같은 개념이기 때문이다.

즉, 간선은 클러스터에 비유하면 네트워크 개념이고, 네트워크로 연결되어 하나의 클러스터를 형성하고 있는 개개의 컴퓨터들을 노드인 것이다.

이러한 그래프에서 연결관계를 표시하는 방법에는 두가지가 있다.

첫째, 인접행렬 방식.

인접행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 특이점으로는 연결되지 않은 노드들 끼리는 무한의 비용이라고 작성한다. 보통 코드 내에서는 논리적으로 정답이 될 수 없는 매우 큰 값(999999) 등의 값으로 초기화 하는 경우가 많다.

INF = 9999999

graph = [
	[0, 7, 5],
	[7, 0, INF],
	[5, INF, 0]
]

둘째, 인접 리스트 방식.

인접 리스트 방식은 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 기록하는 방식이다. 인접 행렬 방식과 같이 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)

보통 인접 리스트 방식이 메모리 사용 측면에서 더 효율적이다.

DFS(Depth-Fist Search)

깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조를 이용하며, 구체적인 동작은 아래와 같다.

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

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

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

# 각 노드의 방문 정보 리스트로 표현
visited = [False] * 9
# [False, False, False, False, False, False, False, False, False]

dfs(graph,1,visited)
# result : 1 2 7 6 8 3 4 5

BFS(Breadth First Search)

너비 우선 탐색이라는 의미를 가지는 알고리즘이다. 가까운 노드부터 탐색하는 알고리즘으로서 가장 멀리있는 노드를 우선적으로 탐색하는 DFS와 정반대의 알고리즘이다. BFS는 큐 자료구조를 이용하며, 구체적인 동작방식은 아래와 같다.

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

from collections import deque

def bfs(graph,start,visited):
    queue = deque()
		# 현재 노드 방문 처리
    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)
# result : 1 2 3 8 7 4 5 6

BFS와 DFS를 간단히 표로 요약하면 다음과 같다.

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용