[알고리즘] 그래프 탐색 알고리즘 DFS/BFS
개념정리
탐색 알고리즘 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정.
스택 자료구조 : 먼저 들어온 데이터가 나중에 나가는 선입후출의 자료구조로, 박스 쌓는 것을 예로 들 수 있음
파이썬에서 스택을 사용하고 싶으면 리스트를 사용하면 스택처럼 사용 할 수 있음.
stack = []
stack.append(1) #1 추가
stack.pop() #마지막 원소 삭제
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)
print(stack[::-1]) #뒤집어서 최상단 원소부터 출력 [5,4,3,2,1]
print(stack) #최하단 원소부터 출력 [1,2,3,4,5]큐 자료구조 : 먼저 들어온 데이터가 먼저 나가는 선입선출의 자료구조, 터널같은 형태를 예로 들 수 있음
파이썬에서 deque를 import해 사용할 수 있음
from collections import 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) #먼저 들어온 순서대로 출력 #실행결과 : deque([3,7,1,4])
queue.reverse() #역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력 #실행결과 : deque([4,1,7,3])
재귀함수 : 자기 자신을 다시 호출하는 함수를 의미
def recursive_function():
print("재귀함수 호출")
recursive_function() #함수 안에서 따로 종료 조건을 명시하지 않으면
recursive_function() #무한으로 재귀함수가 돌게됨
재귀함수 예제 1.
#재귀함수에서 널리 쓰이는 펙토리얼 구현 예제
#case 1. 반복문으로 구현한 n!
def factorial_iterative(n):
result = 1
#1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n+1):
result *= i
return result
#case 2. 재귀함수로 구현한 n!
def factorial_recursive(n):
if n<=1 : #n이 1 이하인 경우 1을 반환
return 1
#n != n*(n-1)! 그대로 코드로 작성하기
return n*factorial_recursive(n-1)
재귀함수 예제 2.
최대공약수(Greatest Common Divisor, GCD)계산 (유클리드 호제법) 예제
두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘은 유클리드 호제법이 있는데,
두 자연수 A,B에 대해 (A>B인 경우) A를 B로 나눈 나머지를 R이라고 할 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
ex) GCD(192, 162) 일 때,
step 1. 162/192 나머지는 30
step 2. 30/162 나머지 12
step 3. 12/30 나머지 6
최대공약수는 6
def gcd(a,b):
if a % b , == 0 :
return b
else :
return gcd(b, a % b)
print(gcd(192, 162))
DFS
DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
DFS는 스택 자료구조 (혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은
1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행 할 수 없을 때까지 반복한다
ex)
#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 = [
[], #0번째 노드는 대개 안쓰므로 비워둠
[2, 3, 8] #1번노드와 인접한 노드들
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
#각 노드가 방문된 정보를 1차원 리스트로 표현
visit = [False] * 9 #0번째 노드는 사용안하므로 1~9까지 나오게 9번 곱함, 기본값은 false
#정의된 DFS 함수를 호출
dfs(graph, 1, visited)
BFS
BFS는 너비 우선 탐색 이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 이다.
BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은
1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 더 이상 2번의 과정을 수행할 수 없을때까지 반복한다.
=> 특히 특정 조건에서 최단거리 측정을 위해 많이 사용
from collections import deque
#BFS 메서드 정의
def bfs(graph, start, visited):
#큐 구현을 위해 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 = [
[],
[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. 음료수 얼려먹기
Q. N*M 크기의 얼음 틀에서 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시한다. 0끼리는 상, 하, 좌, 우로 붙어 있는 경우 서로 연결된 것으로 간주한다. 얼음 틀 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하라
( 4*5 얼음틀에서
00110
00011
11111
00000 모양으로 틀이 주어지면 아이스크림은 총 3개가 생성된다
)
A.
1. DFS를 활용하는 알고리즘
step 1. 특정 지점의 주변 상, 하 좌, 우를 살펴보고 지점 중 값이 0 이면서 아직 방문하지 않은 점이 있다면 해당 지점 방문
step 2. 방문 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면 연결된 모든 지점을 방문할 수 있음.
step 3. 모든 노드에 대해 1~2 과정 반복하며, 방문하지 않은 지점의 수를 카운트
#N, M을 공백 기준으로 구분하여 입력 받기
n,m = map(int, input().split())
#2차원 리스트의 앱 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
#DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y) :
print("현재위치는?",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
#상하좌우 위치들도 모두 재귀적으로 호출
dfs(x-1 , y)
dfs(x, y-1)
dfs(x+1, y)
dfs(x, y+1)
return True #앞선 모든 재귀가 다 끝날때까지는 True가 리턴 안됨.
return False
#모든 노드에 채우기
result = 0
for i in range(n):
for j in range(m):
#현재 위치에서 DFS 수행
if dfs(i,j) == True:
result += 1
print(result)
문제 예제 2. 미로탈출
Q. N*M 크기의 직사각형 미로에 갇혔을 때, 0은 이동 불가 1은 이동 가능하다, 탈출할 최소 칸의 개수는? (시작 칸과 마지막 칸을 모두 포함해서 계산)
A.BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색.
from collections import deque
#N,M을 공백을 기준으로 구분하여 입력 받기
n,m = map(int, input().split())
#2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
#이동할 네 가지 방향 정의 (좌우상하)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
#BFS소스코드 구현
def bfs(x,y):
#큐 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x,y))
#큐가 빌 때까지 반복
while queue:
x,y = queue.popleft()
#현재 위치에서 4가지 방향으로의 위치 확인
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))
print("큐 추가 : ", (nx, ny))
#가장오른쪽 아래까지 최단거리 반환
return graph[n-1][m-1]
print(bfs(0,0))
DFS랑 BFS는 눈으로 보이게 손으로 정사각판을 그려야 아직 이해가 되는 수준이라, 해당 알고리즘 유형의 문제들을 몇개 더 풀어보면서 심화 시키는 다음 포스트를 정리할 예정!