📍 그래프 탐색 알고리즘 - DFS / BFS
탐색(Search)이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다.
대표적인 그래프 탐색 알고리즘으로 DFS, BFS가 있다.
DFS, BFS는 코딩 테스트에서 매우 자주 등장하는 유형이다. (특히 국내 대기업 공채)
이 DFS, BFS를 배우기전에 알고가야할 자료구조를 알아보자.
📍 DFS (Depth - First Search)
- DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
- DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.
1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
🔎 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 = [
[], # 보통 노드는 1번부터 시작하므로 인덱스 0은 비움
[2, 3, 8], # 1번 노드와 연결된 2, 3, 8번 노드
[1, 7], # 2번 노드와 연결된 1, 7번 노드
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
# default는 False
visited = [False] * 9 # 인덱스 0은 사용 X, 노드8개+1의 크기의 리스트
# 정의된 DFS 함수 호출
dfs(graph, 1, visited) # 출력: 1 2 7 6 8 3 4 5📍 BFS (Breath - First Search)
- BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
- BFS는 큐 자료구조를 이용하며, 구체적인 동작과정은 다음과 같다.
1. 탐색 시작 노드를 큐에 삼입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. - 각 간선의 비용이 모두 동일한 상황에서 최단 거리 문제 해결하는 목적으로 사용
🔎 BFS 예제 )
from collections import deque
# BFS 메서드 정의
def bfs(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] = True
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
# 인접리스트 방식으로 그래프 표현
graph = [
[], # 보통 노드는 1번부터 시작하므로 인덱스 0은 비움
[2, 3, 8], # 1번 노드와 연결된 2, 3, 8번 노드
[1, 7], # 2번 노드와 연결된 1, 7번 노드
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
# default는 False
visited = [False] * 9 # 인덱스 0은 사용 X, 노드8개+1의 크기의 리스트
# 정의된 DFS 함수 호출
bfs(graph, 1, visited) # 출력: 1 2 3 8 7 4 5 6📌 예제
• 예제 1 ) 음료수 얼려 먹기 - DFS
# N X M 크기의 얼음 틀이 있다.
# 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1 표시
# 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우
# 서로 연결되어 있는 것으로 간주
# 이때 얼음 틀의 모양이 주어졌을 때 생성되는
# 총 아이스크림의 개수를 구하는 프로그램을 작성
# 연결요소 찾는 문제!
def dfs(x, y):
if x <= -1 or x >= n or y <= -1 or y >= m: # 범위 벗어나면
return False # 즉시 종료
if graph[x][y] == 0: # 현재 노드가 방문 X면
graph[x][y] = 1 # 방문 처리
# 상/하/좌/우 방문 처리 재귀 호출
# return 값 사용 X 단순히 연결된 모든 노드 방문 처리
dfs(x-1, y)
dfs(x+1, y)
dfs(x, y-1)
dfs(x, y+1)
return True
return False
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 모든 노드에 음료수 채우기
cnt = 0
for i in range(n):
for j in range(m):
if dfs(i, j) == True: # 방문처리를 처음하는 시작 노드만
cnt += 1 # 카운트
print(cnt)• (0, 0) 부터 시작해서 아직 방문하지 않은 노드(0)인 경우 카운트를 하고
그 노드의 상/하/좌/우를 방문 처리한다.
• 다시 탐색하며 방문하지 않은 노드를 찾았을 때 또 카운트를 하다보면 1로 분리된 0의 그룹이
각 +1씩 카운트되므로 이 cnt를 출력하면 답이 된다.• 예제 2 ) 미로 탈출 - BFS
# 동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혔다.
# 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.
# 동빈이의 위치는 (1, 1)이며 미로의 출구는 (N, M)의 위치에 존재하고
# 한 번에 한 칸씩 이동할 수 있다.
# 이때 괴물이 있는 부분은 0으로 없는 부분은 1로 표시되어 있다.
# 미로는 반드시 탈출할 수 있는 형태로 제시된다.
# 이때, 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개순느?
# 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해 계산한다.
from collections import deque
def bfs(x, y):
queue = deque()
queue.append((x, y))
# 큐가 빌 때까지 반복
while queue:
x, y = queue.popleft()
for i in range(4): # 현재 위치에서 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())))
# 4가지 이동 방향 정의 (상/하/좌/우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
print(bfs(0, 0))• (0, 0) 부터 시작해서 상/하/좌/우 를 살피며 괴물이 없는 1인 노드를 찾는다.
• 그 노드에 전 노드의 값 + 1을 넣는다 (이동 거리 누적)
• 그 노드의 좌표값을 다시 큐에 넣고 반복하다가 큐가 비면(탐색할 노드가 없으면) 반복문을 탈출한다.
• 마지막 노드의 값을 출력하면 최단 거리 값이 나온다.🙏 참고
매일 성장하는 예비 웹 개발자 🌱