[03] DFS/BFS

탐색(search)

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

 

대표적인 탐색 알고리즘 : DFS/BFS

제대로 이해하기 위해 기본적인 자료구조인 스택, 큐에 대한 이해 필요

 

 

자료구조(Data Structure)

데이터를 표현하고 관리하고 처리하기 위한 구조

기초 개념 : 스택, 큐

 

핵심 함수

삽입(push) : 데이터를 삽입한다.

삭제(pop) : 데이터를 삭제한다.

 

* 오버플로우(Overflow) : 특정 자료구조가 수용할 수 있는 데이터의 크기가 가득 찬 상태에서 삽입 연산 수행 시 발생

언더플로우(Underflow) : 특정 자료구조에 데이터가 들어있지 않은 상태에서 삭제 연산 수행 시 발생

 

 

스택(stack)

후입선출(Last In First Out) 구조

 

초기단계 [   ,   ,   ,   ,   ]

push(5) [ 5,   ,   ,   ,   ]

push(2) [ 5, 2,   ,   ,   ]

push(3) [ 5, 2, 3,   ,   ]

push(7) [ 5, 2, 3, 7,   ]

pop() [ 5, 2, 3,   ,   ]

push(4) [ 5, 2, 3, 4,   ]

push(1) [ 5, 2, 3, 4, 1 ]

pop() [ 5, 2, 3, 4,   ]

pop() [ 5, 2, 3,   ,   ]

 

파이썬 코드로 표현

stack = []

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

print(stack) #[5, 2, 3]
print(stack[::-1]) #[3, 2, 5]

파이썬에서 스택을 이용할 때는 별도의 라이브러리가 필요가 없음

 

 

큐(Queue)

선입선출(First In First Out) 구조

 

초기 단계 []

push(5) [ 5   ]

push(2) [ 5, 2 ]

push(3) [ 5, 2, 3  ]

push(7) [ 5, 2, 3, 7 ]

pop() [ 2, 3, 7 ]

push(4) [ 2, 3, 7, 4  ]

push(1) [ 5, 2, 3, 4, 1 ]

pop() [ 2, 3, 4, 1 ]

pop() [ 3, 4, 1 ]

 

파이썬 코드로 표현

from collections import deque

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

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

print(queue) #deque([3, 4, 1])
queue.reverse()
print(queue) #deque([1, 4, 3])

deque 라이브러리가 queue 라이브러리르 이용하는 것 보다 효율적이고 간단하다.

 

deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 메소드 이용

 

 

재귀 함수(Recursive Function)

자기 자신을 다시 호출하는 함수

 

ex.

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

 

재귀 함수를 문제 풀이에서 사용될 때는 종료 조건을 꼭 명시해야 함

 

ex. 재귀 함수를 100번 호출

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

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용함

 

== 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀 함수를 이용해서 구현될 수 있음

ex. DFS

 

 

DFS(Depth-First Search)

깊이 우선 탐색

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

 

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

인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

 

인접 행렬(Adjacency Matrix) 방식 : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

연결된 그래프를 인접 행렬로 표현할 때 파이썬에서는 2차원 리스트로 구현할 수 있다.

(연결되지 않은 노드끼리는 무한의 비용이라고 작성한다.)

INF = 999999999 #무한의 비용 선언

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

print(graph) #[[0,7,5],[7,0,999999999],[5,999999999,0]]

 

인접 리스트(Adjacency List) 방식 : '연결 리스트'라는 자료구조를 이용해 구현

리스트 자료형이 append()와 메소드를 제공하므로, 단순히 2차원 리스트를 이용

 

ex. 그래프를 인접 리스트 방식으로 처리할 때 데이터를 초기화한 코드

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

print(graph) #[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

 

위의 두 방식의 차이(메모리와 속도 측면) :

1. 메모리 측면

인접 행렬 방식 - 모든 관계를 저장하므로 노드 개수가 많을수록 메모리 낭비

인접 리스트 방식 - 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용

(그렇기 때문에 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 더 느리다.)

 

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)

# 1 2 7 6 8 3 4 5

 

 

BFS(Breadth First Search)

'너비 우선 탐색'

가까운 노드부터 탐색하는 알고리즘

 

구현 시 선입선출 방식인 큐 자료구조를 이용하는 것이 정석

인접한 노드를 반복적으로 큐에 넣도록 작성하면 가까운 노드부터 탐색을 진행

실제로 구현할 때 deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요

일반적인 경우 실제 수행시간은 DFS 보다 좋은 편이다.

 

알고리즘의 동작 방식

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

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

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

 

dfs 예제

from collections import deque

# BFS 메서드 정의
def dfs(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] = Ture
                
    # 각 노드가 연결된 정보를 리스트 자료형으로 표현(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)

# 1 2 3 8 7 4 5 6