[이코테] DFS/BFS
DFS / BFS 에 필요한 자료구조
1. 스택
stack = []
stack.append(5)
stack.append(4)
stack.append(3)
stack.pop()
print(stack) # 5, 4
print(stack[::-1]) # 4, 5
2. 큐
from collections import deque
queue = deque()
queue.append(5)
queue.append(4)
queue.append(3)
queue.popleft()
print(queue) # 4, 3
queue.reverse() #역순으로 바꾸기
print(queue) # 3, 4
재귀함수
종료조건
재귀함수가 언제 끝날지 종료 조건을 반드시 명시해야 함
수행에 스택 자료구조를 사용함 (마지막에 호출한 함수가 종료되어야 그 앞의 함수 호출이 종료되기 때문)
재귀함수를 사용했을 때의 이점
점화식을 그대로 옮겨놨기 때문에 가독성이 좋고 간결하다 (팩토리얼의 경우)
DFS vs BFS
| DFS | BFS |
| 최대한 멀리 있는 노드부터 | 가장 가까운 노드부터 |
| 스택 | 큐 |
| 재귀 이용 | 큐 이용 |
DFS
깊이우선 탐색
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
그래프는 노드와 간선으로 이루어지고 노드를 정점 (vertex) 라고 하기도 함
최대한 멀리 있는 노드를 우선적으로 탐색
DFS 를 표현하는 두가지 방법
1. 인접 행렬 방식
INF = 99999999
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
연결되어 있지 않은 노드의 경우에는 INF(무한)
2. 인접 리스트 방식
자료구조 연결리스트를 이용하여 구현
모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해서 저장
ex)
0 - 1 - 2
1 - 0
2 - 0
이라면 2는 1과 연결되지 않고, 1은 2와 연결되지 않은 것.
두 방식의 비교
인접 행렬 방식의 단점
- 모든 관계를 저장하기 때문에 노드의 개수가 많을수록 비효율적
인접 행렬 방식의 장점
- 특정한 두 노드가 연결되어 있는지 빠르게 확인 가능
ex) graph[1][7] 을 통해서 1과 7이 연결되어 있는지 확인할 수 있음
반면 인접리스트방식의 경우에는 앞에서부터 차례대로 확인해야 함
인접 리스트 방식의 장점
- 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용
DFS 의 동작 방식
1. 시작 노드를 스택에 삽입, 방문 처리
2. 스택의 최상단 노드에 연결된 방문하지 않은 인접한 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리
방문하지 않은 인접한 노드가 없으면 해당 노드를 스택에서 꺼내기
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복하기
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
너비 우선 탐색
가까운 노드부터 탐색
인접한 노드를 반복적으로 큐에 넣도록
BFS 의 동작 방식
1. 탐색 시작 노드를 큐에 삽입 / 방문처리
2. 큐에서 노드를 꺼내서 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입
3. 2번의 과정을 반복
from collections import deque
def dfs(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
dfs(graph, 1, visited)
* 2차원 배열의 탐색 문제를 만났을 때 그래프로 바꿔서 생각하면 더 쉽게 풀이할 수 있음
실전 문제
1. 음료수 얼려 먹기
# p.149 실전문제 3 음료수 얼려 먹기
n,m = map(int,input().split())
graph = [
list(map(int,input()))
for _ in range(n)
]
visited = [
[False for _ in range(m)]
for _ in range(n)
]
cnt = 0
def in_range(x,y):
return x<n and y<m and x>=0 and y>=0
def bfs(x, y):
if not in_range(x,y): #범위를 넘어가면 false 반환
return False
if not visited[x][y] and graph[x][y]==0:
visited[x][y] = True
#연결된 노드 전부, 즉 상하좌우로 방문
bfs(x-1,y)
bfs(x,y-1)
bfs(x,y+1)
bfs(x+1,y)
return True
return False
for i in range(n):
for j in range(m):
if bfs(i,j)==True:
cnt+=1
print(cnt)
우선, 얼음틀을 넘어가면 False 를 반환하도록 했다.
연결된 노드를 전부 방문해야 하는데 얼음틀의 경우에는 연결된 노드가 인접한 상하좌우이기 때문에 해당 노드를 전부 방문하도록 했다. 그러나 해당 부분을
1. 이미 방문했거나,
2. 막혀있는 경우에는
더 이상 갈 수 없기 때문에 해당 경우에는 False 를 반환하도록 했다.
상하좌우를 방문하며 방문 할 수 있는 노드에는 visited 배열에 True 로 표시될 것이기 때문에 각 노드를 시작점으로 잡고, True 인 경우의 개수를 세면 최종적으로 아이스크림의 개수를 구할 수 있다.
2. 미로 탈출
from collections import deque
n,m = map(int,input().split())
graph = []
for _ in range(n):
graph.append(list(map(int,input())))
# 1로만 움직일 수 있음
# 움직여야 하는 칸의 개수
dxs = [-1, 1, 0, 0]
dys = [0, 0, -1, 1]
def in_range(x,y):
return x<n and y>=0 and x>=0 and y<m
def bfs(x,y):
queue = deque() #방문한 곳들
queue.append((x,y)) #시작 위치 우선 큐에 넣고 시작
while queue:
x,y = queue.popleft() #인접한 노드의 위치
for i in range(4):
new_x = x+dxs[i]
new_y = y+dys[i]
if in_range(new_x,new_y) and graph[new_x][new_y]!=0 and graph[new_x][new_y]==1:
graph[new_x][new_y] = graph[x][y]+1
queue.append((new_x,new_y))
bfs(0,0)
print(graph[n-1][m-1])너비 우선 탐색을 이용한 문제다.
범위 내에 있고, 괴물이 없으면 이동할 수 있다.
또한, 새로 방문한 경우에만 거리를 업데이트 해준다.
새로 방문한 경우가 아닌 경우에 거리를 업데이트 해주게 되면 최단 거리를 업데이트 하는 것이 아니기 때문이다.