DFS/BFS
탐색(search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.
대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.
스택
스택은 먼저 들어온 데이터가 나중에 나가는 후입선출(LIFO: Last-In First-Out) 방식 의 자료구조이다.
큐
큐는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First-In First-Out) 방식의 자료구조이다.
재귀 함수
재귀 함수(recursive function)는 자기 자신을 다시 호출하는 함수를 의미한다.
재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 명시해야 한다.
def recursive_function(i):
if i == 100:
return i
print(i, i + 1)
recursive_function(i + 1)
print(i)
recursive_function(1)재귀 함수 - 팩토리얼
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
print(factorial_iterative(5))def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
print(factorial_iterative(5))재귀 함수 - 유클리드 호제법 (최대공약수 계산)
유클리드 호제법은 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘이다.
두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라 가정한다.
이 때 A, B의 최대공약수는 B와 R의 최대공약수와 같다.
def greatest_common(A, B):
if A % B == 0:
return B
else:
return greatest_common(B, A % B)
print(greatest_common(192, 162))모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
스택 대신 재귀 함수를 사용하는 경우가 많다.
DFS (Depth-First Search)
DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS는 스택 자료구조에서(혹은 재귀 함수)를 이용하여 구현할 수 있다.
-
탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.
-
스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
def depth_first(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
depth_first(graph, i, visited)
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * 9
depth_first(graph, 1, visited)BFS (Breadth-First Search)
BFS는 너비 우선 탐색이라고 부르며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
BFS는 큐 자료구조를 이용하여 구현할 수 있다.
-
탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
-
큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
-
2번 과정을 수행할 수 없을 때까지 반복한다.
def breadth_first(graph, start, visited):
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
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * 9
breadth_first(graph, 1, visited)DFS/BFS - 음료수 얼려 먹기
DFS를 이용한 풀이
-
특정한 지점의 상하좌우를 살펴본 후 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
-
방문한 지점에서 다시 상하좌우를 살펴 보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문할 수 있다.
-
모든 노드에 대하여 1~2번 과정을 반복하며, 방문하지 않은 지점의 수를 카운트한다.
import sys
sys.stdin = open("음료수 얼려 먹기.txt", 'r')
input = sys.stdin.readline
def depth_first(x, y):
if x <= -1 or x >= N or y <= -1 or y >= M:
return False
if graph[x][y] == 0:
graph[x][y] = 1
depth_first(x - 1, y)
depth_first(x, y - 1)
depth_first(x + 1, y)
depth_first(x, y + 1)
return True
return False
N, M = map(int, input().split())
graph = []
for i in range(N):
graph.append(list(map(int, input().rstrip())))
result = 0
for i in range(N):
for j in range(M):
if depth_first(i, j) == True:
result += 1
print(result)DFS/BFS - 미로 탈출
BFS를 이용한 풀이
-
(1, 1)의 노드에서 시작한다.
-
(1, 1)의 위치에서 상하좌우를 탐색하여 (1, 2)의 노드를 방문하고 새롭게 방문하는 (1, 2)의 노드의 값을 2로 바꾼다.
import sys
from collections import deque
sys.stdin = open("미로 탈출.txt", 'r')
input = sys.stdin.readline
def breadth_first(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= N or ny < 0 or ny >= M:
continue
if graph[nx][ny] == 0:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
return graph[N - 1][M - 1]
N, M = map(int, input().split())
graph = []
for i in range(N):
graph.append(list(map(int, input().rstrip())))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
print(breadth_first(0, 0))