[TIL] DFS & BFS (feat. 스택, 큐 , 재귀 함수) - (1) 이론

[Today I Learned]

#  스택 

- 선입후출 자료구조

 

- Python에서는 List로 구현

stack = [ ]

stack.append(5) # [5]
stack.append(2) # [5,2]
stack.pop() # [5]
stack.append(1) # [5,1]
stack.append(4) # [5,1,4]

print(stack[::-1]) # 최상단 원소부터 출력 ; [4,1,5]
print(stack) # 최하단 원소부터 출력 ; [5,1,4]

 

#  큐

- 선입선출 자료구조

- Python에서는 Collections.deque(덱)으로 구현

- List로도 구현할 수 있지만 시간 복잡도 이슈. (특정 인덱스의 원소 꺼내는 pop 연산 후에, 전체적으로 인덱스 재조정하는 과정 필요.)

from collections import deque

queue = deque()

queue.append(5) # [5]
queue.append(2) # [5,2]
queue.popleft() # [2]
queue.append(1) # [2,1]
queue.append(4) # [2,1,4]

print(queue) # 먼저 들어온 순서대로 출력 ; deque([2,1,4])

queue.reverse
print(queue) # 나중에 들어온 원소부터 출력 ; deque([4,1,2])

 

#  재귀 함수

- 자기 자신을 다시 호출하는 함수
- DFS를 실질적으로 구현하고자할 때 자주 사용되는 방법

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

 

- 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력됨. (Python 기준)
- 따라서 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건 반드시 명시해야

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

호출 > 종료

 

+ 유의사항

- 모든 재귀 함수는 반복문을 이용해 동일한 기능을 구현할 수 있음
- 재귀 함수가 반복문보다 유리한 경우도 있고, 불리한 경우도 있음

- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임. 그래서 스택을 사용해야할 때 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음

 

#  DFS (Depth-First Search)

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

- 스택 혹은 재귀 함수를 이용해 구현

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

 

- 동작 예시

1 > 2 > 7 > 6 > 8 > 3 > 4 > 5

 

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
	[], # 노드 번호를 바로 사용할 수 있도록 일부러 비워둠
    [2,3,8],
    ...
]

visited = [False] * 9


def dfs(graph, v, visited):
	visited[v] = True
    
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
dfs(grpah,1,visited)

 

#  BFS (Breadth-First Search)

- 너비 우선 탐색 알고리즘 ; 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

- 큐 자료구조 이용

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

 

- 동작 예시

1 > 2 > 3 > 8 > 7 > 4 > 5 > 6

from collections import deque

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
	[], # 노드 번호를 바로 사용할 수 있도록 일부러 비워둠
    [2,3,8],
    ...
]

visited = [False] * 9


def bfs(graph, start, visited):
	queue = deque([start])
    
    visited[start] = True
    
    while queue:
    	v = queue.popleft()
        
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
            
bfs(grpah,1,visited)

 

+ 각 간선의 비용이 모두 동일한 상황에서, 최단 거리 문제를 해결하기 위한 목적으로 사용될 수 있음

 

역시 발등에 불이 떨어지니까 눈에 좀 들어온다,,ㅎㅎ