DFS / BFS
그래프를 탐색하기 위한 대표적인 두 가지 알고리즘
1. 꼭 필요한 자료구조 기초
탐색
- 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
자료구조
- 데이터를 표현하고 관리하고 처리하기 위한 구조
삽입 (Push) : 데이터를 삽입
삭제 (Pop) : 데이터를 삭제
스택
선입후출 (First In Last Out) 또는 후입선출 (Last In First Out)
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) # 최하단 원소부터 출력 [5, 2, 3, 1]
print(stack[::-1]) # 최상단 원소부터 출력 [1, 3, 2, 5]큐
선입선출 (First In First Out)
from collections import deque
# 큐(Queue) 구현을 위해서는 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) # 먼저 들어온 순서대로 출력 [3, 7, 1, 4]
queue.reverse()
print(queue) # 나중에 들어온 원소부터 출력 [4, 1, 7, 3]재귀 함수
자기 자신을 다시 호출하는 함수
# 반복적으로 구현한 n!
def factorial_iterative(n) :
result = 1
# 1부터 n까지 수를 곱하기
for i in range(1, n + 1) :
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n) :
if n <= 1 :
return 1
# n! = n * (n - 1)!
return n * factorial_recursive(n - 1)
print("반복적으로 구현 : ", factorial_iterative(5))
print("재귀적으로 구현 : ", factorial_recursive(5))2. 탐색 알고리즘 DFS / BFS
DFS (Depth-First Search)
-
깊이 우선 탐색
-
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
인접행렬 (Adjacency Matrix)
2차원 배열로 그래프의 연결 관계를 표현하는 방식인접 리스트 (Adjacency Matrix)
리스트로 그래프의 연결 관계를 표현하는 방식- 탐색 시작 노드를 스택에 삽입하고 방문처리
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
# 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)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
dfs(graph, 1, visited)BFS (Breath First Search)
-
너비 우선 탐색
-
가까운 노드부터 탐색하는 알고리즘
- 탐색 시작 노드를 큐에 삽입하고 방문처리
- 큐에 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐네 삽입하고 방문처리
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
from collections import deque
def bfs(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
bfs(graph, 1, visited)3. 음료수 얼려 먹기
음료수 얼려 먹기
💡 DFS로 해결
n, m = map(int, input().split()) # n X m
# 2차원 리스트 맵 정보
graph = []
for i in range(n) :
graph.append(list(map(int, input())))
def dfs(x, y) :
if x <= -1 or x >= n or y <= -1 or y >= m :
return False
# 0인 경우
if graph[x][y] == 0 :
# 해당 노드 1로 변경
graph[x][y] = 1
# 상, 하, 좌, 우 위치 재귀적 호출 > 0인 경우 1로 변경
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
return True
return False
result = 0
for i in range(n) :
for j in range(m) :
if dfs(i, j) == True :
result += 1
print(result)4. 미로 탈출
미로 탈출
💡 BFS로 해결
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n) :
graph.append(list(map(int, input())))
# 상 하 좌 우 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(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 ny < 0 or nx >= n or ny >= m :
continue
# 값이 0인 경우
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]
print(bfs(0, 0))