알고리즘
[알고리즘] dfs / bfs 정리
j9972
2022. 9. 16. 14:59
728x90
DFS/BFS - 그래프 탐색 알고리즘
트리가 깊고 해답이 깊은곳에 있다면 dfs
트리의 뿌리 근처에 해답이 있는거 같다면 bfs
1. 스택 자료구조 ( 선입 후출) - 입구와 출구가 같음
- 삽입, 삭제 → append, pop → O(1)
- 리스트 자료형 쓰기
stack = []
stack.append(5)
stack.append(2)
stack.append(4)
stack.pop() # stack = {5,2}
print(stack[::-1]) #최상단 원소부터 출력 [2,5]
print(stack) # 최하단 원소부터 출력 [5,2]
2. 큐 자료구조 (선입선출) - 입구 ≠ 출구
- 삽입, 삭제 → append, popleft()
- deque 라이브러리 사용 ( 리스트 사용 안함 )
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft()
print(queue) # [2,3]
queue.reverse()
print(queue) #[3,2]
3. 재귀함수 - 자기 자신을 다시 호출
- 종료조건 필수
- dfs쓸때, stack으로 사용 가능 ( stack대신에 재귀를 많이 사용함 )
# 예시 1) 팩토리얼
# 1. 반복문
def fact(n):
res = 1
for i in range(1,n+1):
res *= i
return res
# 2. 재귀문
def fact(n):
if n <= 1:
return 1 # 종료조건
return n * fact(n-1)
# 예시 2) 유클리드 호제법 -> 두 자연수에 대한 최대 공약수 구하기
# A>B -> R이 나머지: A,B의 최대공약수 = B,R의 최대공약수 ( 반복 )
def gcd(a,b):
if a%b == 0:
return b
else:
return gcd(b, a%b)
print(gcd(192,162))
DFS ( 깊이우선 → stack or 재귀)
- 방문 기준에 따라 어떤 인접 노드에 접근하는지 달라짐 ( 보통은 낮은 숫자 순서)
- 방법
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 인접한 노드중 1개라도 방문하지 않은 노드가 있다면, 스택에 넣고 방문처리함
- 인접한 노드중 1개라도 방문하지 않은 노드가 없다면, 스택에 최상위 노드를 꺼내
graph = [
[], # idx = 0인 부분 비워두기
[2,3,8], # idx = 1번 노드의 주변 노드 idx
[1,7], # idx = 2번 노드의 주변 노드 idx
[1,4,5], # idx = 3번 노드의 주변 노드 idx
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
#각 노드가 방문된 정보 표현 ( 1차원 )
visited = [False]*9
#기본적으로 false로해서 방문하지 않음으로 초기화하기, idx=0 은 비우기위해 8이 아닌 9
#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)
#정의된 함수 호출
dfs(graph, 1, visited)
BFS (너비우선 → 그래프에서 가까운 노드 우선 탐색)
- 큐사용 ( deque )
- 특정 노드에서 최단 경로를 구할때도 사용함
- 간선 비용이 동일하면 bfs
- 방법
- 탐색 시작노드를 queue에 삽입, 방문 처리
- 큐에서 노드를 꺼낸뒤 → 인접 노드중 방문하지 않은 노드를 모두 큐에 삽입 → 방문처리
graph = [
[], # idx = 0인 부분 비워두기
[2,3,8], # 1번 노드 주변의 노드 idx
[1,7], # 2번 노드 주변의 노드 idx
[1,4,5], # 3번 노드 주변의 노드 idx
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
#각 노드가 방문된 정보 표현 ( 1차원 )
visited = [False]*9
#기본적으로 false로해서 방문하지 않음으로 초기화하기, idx=0은 비우기위해 8이 아닌 9
#bfs 함수 정의
from collection 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
#정의된 함수 호출
bfs(graph, 1, visited)
문제1) 음료수 얼려 먹기
수행과정
- N*M 얼음틀, 구멍이 뚫린 부분이 0, 칸막이 있는 부분이 1 ( 세로n, 가로 m )
- n*m이면 5개짜리 배열이 4개 [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20]]
- 0인부분 즉, 구멍이 뚫린 부분은 상하좌우 (연결된걸로 간주) → 이 부분이 dfs or bfs 써야 함을 의미
- 아이스크림 개수 구하기
idea
- 특정 노드에서 이동가능한 모든 노드를 방문처리하기
- DFS → 특정 지점에서 주변 노드중 값이 0이면서, 방문하지 않은 지점 방문
n,m = map(int,input().split())
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
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
return False
res = 0 #카운트 하는것
for i in range(n):
for j in range(m):
if dfs(i,j) == True: # 현 위치에서 dfs 수행
res += 1
print(res)
- 모든 노드를 탐색해야하면 bfs ( que ) , 주변 노드만 탐색 bfs ( stack - 재귀 )
문제2) 미로 탈출
수행과정
- N * M, (1,1)에서 1칸씩 이동해서 출구로 가기(N,M)
- 탈출을 위해 최소한으로 이동하는 칸의 개수 세기
- 괴물 있음 = 0, 괴물 없음 = 1
- 칸을 카운트 할때는, 시작 과 끝 칸들도 모두 포함
idea
- BFS - 간선의 비용이 모두 같으며, 모든 노드를 탐색해야하므로 최단거리 구하기일때 사용함
DFS/BFS - 그래프 탐색 알고리즘
트리가 깊고 해답이 깊은곳에 있다면 dfs
트리의 뿌리 근처에 해답이 있는거 같다면 bfs
1. 스택 자료구조 ( 선입 후출) - 입구와 출구가 같음
- 삽입, 삭제 → append, pop → O(1)
- 리스트 자료형 쓰기
stack = []
stack.append(5)
stack.append(2)
stack.append(4)
stack.pop() # stack = {5,2}
print(stack[::-1]) #최상단 원소부터 출력 [2,5]
print(stack) # 최하단 원소부터 출력 [5,2]
2. 큐 자료구조 (선입선출) - 입구 ≠ 출구
- 삽입, 삭제 → append, popleft()
- deque 라이브러리 사용 ( 리스트 사용 안함 )
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft()
print(queue) # [2,3]
queue.reverse()
print(queue) #[3,2]
3. 재귀함수 - 자기 자신을 다시 호출
- 종료조건 필수
- dfs쓸때, stack으로 사용 가능 ( stack대신에 재귀를 많이 사용함 )
# 예시 1) 팩토리얼
# 1. 반복문
def fact(n):
res = 1
for i in range(1,n+1):
res *= i
return res
# 2. 재귀문
def fact(n):
if n <= 1:
return 1 # 종료조건
return n * fact(n-1)
# 예시 2) 유클리드 호제법 -> 두 자연수에 대한 최대 공약수 구하기
# A>B -> R이 나머지: A,B의 최대공약수 = B,R의 최대공약수 ( 반복 )
def gcd(a,b):
if a%b == 0:
return b
else:
return gcd(b, a%b)
print(gcd(192,162))
DFS ( 깊이우선 → stack or 재귀)
- 방문 기준에 따라 어떤 인접 노드에 접근하는지 달라짐 ( 보통은 낮은 숫자 순서)
- 방법
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 인접한 노드중 1개라도 방문하지 않은 노드가 있다면, 스택에 넣고 방문처리함
- 인접한 노드중 1개라도 방문하지 않은 노드가 없다면, 스택에 최상위 노드를 꺼내
graph = [
[], # idx = 0인 부분 비워두기
[2,3,8], # idx = 1번 노드의 주변 노드 idx
[1,7], # idx = 2번 노드의 주변 노드 idx
[1,4,5], # idx = 3번 노드의 주변 노드 idx
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
#각 노드가 방문된 정보 표현 ( 1차원 )
visited = [False]*9
#기본적으로 false로해서 방문하지 않음으로 초기화하기, idx=0 은 비우기위해 8이 아닌 9
#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)
#정의된 함수 호출
dfs(graph, 1, visited)
BFS (너비우선 → 그래프에서 가까운 노드 우선 탐색)
- 큐사용 ( deque )
- 특정 노드에서 최단 경로를 구할때도 사용함
- 간선 비용이 동일하면 bfs
- 방법
- 탐색 시작노드를 queue에 삽입, 방문 처리
- 큐에서 노드를 꺼낸뒤 → 인접 노드중 방문하지 않은 노드를 모두 큐에 삽입 → 방문처리
graph = [
[], # idx = 0인 부분 비워두기
[2,3,8], # 1번 노드 주변의 노드 idx
[1,7], # 2번 노드 주변의 노드 idx
[1,4,5], # 3번 노드 주변의 노드 idx
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
#각 노드가 방문된 정보 표현 ( 1차원 )
visited = [False]*9
#기본적으로 false로해서 방문하지 않음으로 초기화하기, idx=0은 비우기위해 8이 아닌 9
#bfs 함수 정의
from collection 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
#정의된 함수 호출
bfs(graph, 1, visited)
문제1) 음료수 얼려 먹기
수행과정
- N*M 얼음틀, 구멍이 뚫린 부분이 0, 칸막이 있는 부분이 1 ( 세로n, 가로 m )
- n*m이면 5개짜리 배열이 4개 [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20]]
- 0인부분 즉, 구멍이 뚫린 부분은 상하좌우 (연결된걸로 간주) → 이 부분이 dfs or bfs 써야 함을 의미
- 아이스크림 개수 구하기
idea
- 특정 노드에서 이동가능한 모든 노드를 방문처리하기
- DFS → 특정 지점에서 주변 노드중 값이 0이면서, 방문하지 않은 지점 방문
n,m = map(int,input().split())
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
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
return False
res = 0 #카운트 하는것
for i in range(n):
for j in range(m):
if dfs(i,j) == True: # 현 위치에서 dfs 수행
res += 1
print(res)
- 모든 노드를 탐색해야하면 bfs ( que ) , 주변 노드만 탐색 bfs ( stack - 재귀 )
문제2) 미로 탈출
수행과정
- N * M, (1,1)에서 1칸씩 이동해서 출구로 가기(N,M)
- 탈출을 위해 최소한으로 이동하는 칸의 개수 세기
- 괴물 있음 = 0, 괴물 없음 = 1
- 칸을 카운트 할때는, 시작 과 끝 칸들도 모두 포함
idea
- BFS - 간선의 비용이 모두 같으며, 모든 노드를 탐색해야하므로 최단거리 구하기일때 사용함