DFS & BFS - 그래프를 탐색하기 위한 알고리즘
DFS
깊이 우선 탐색. 스택이나 재귀를 사용해서 구현
DFS + 스택
- 탐색을 시작할 노드를 스택에 삽입, 방문 처리
- 스택의 최상단에 있는 노드에 방문하지 않은 노드가 하나라도 있으면 스택에 넣고 방문 처리
해당 최상단 노드와 인접한 모든 노드가 전부 방문되었거나 인접한 노드가 없으면 스택에서 꺼냄 - 스택이 빌 때까지 반복
방문 시점: 스택에 삽입하기 전
영상에서는 BFS의 경우엔 큐에 해당 노드의 인접한 노드를 전부 넣고, DFS의 경우엔 스택에 해당 스택 최상단 노드의 인접한 노드를 하나만 넣는다는 점에서 차이가 있다고 했다
다만 인터넷에서 소스코드를 찾아보니 DFS도 BFS와 마찬가지로 스택에서 pop한 노드를 방문처리한 해당 노드와 인접한 자식 노드를 전부 넣어주고 이 과정을 스택이 빌 때까지 반복하는 코드가 많았다
나도 전공수업에서 영상에서 나온 첫번째 방식대로 구현하는 걸로 배웠는데, 두 번째 방법이 반복문 코드로 구현하기 더 쉬워서 그런건지 동일한 노드를 여러번 스택에 넣지 않기 위해 그런건지는 잘 모르겠지만 두 번째 방식으로 구현한 블로그가 많았다.
참고:
https://juhee-maeng.tistory.com/25
https://velog.io/@dltmdrl1244/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%9E%98%ED%94%84-%ED%83%90%EC%83%89-DFS-BFS
두 번째 방식으로 구현했을 때 로직은 아래와 같다
- 탐색을 시작할 노드를 stack에 push
- 스택에서 pop
pop한 정점이 방문하지 않은 정점이라면 방문 처리하고 pop한 정점과 인접했지만 방문하지 않은 정점을 전부 push (이 때 정점의 넘버가 작은 것부터 방문하고 싶으면 큰 정점부터 push)
이미 방문한 정점이라면 무시 - 큐가 빌 때까지 반복
방문 시점: 스택에서 pop한 뒤
DFS + 재귀
수도코드 (DFS + 스택 + 인접리스트)
stack = []
visitied = []
graph -> 2차원 배열로 이루어진 인접리스트
stack.append(start) # 시작 정점을 스택에 넣어줌
while(큐가 빌 때꺄지):
스택에서 node pop
if (node가 방문 안되어있으면):
visited 배열에 pop한 node 방문 처리
pop한 정점과 인접하지만 방문 안한 정점을 전부 stack에 넣어줌
코드 (DFS + 스택 + 인접리스트)
stack = []
visitied = []
graph -> 2차원 배열로 이루어진 인접리스트
stack.append(start) # 시작 정점을 스택에 넣어줌
while(큐가 빌 때꺄지):
node = stack.pop()
if (visited[node] != 1):
visited[node] = 1 # visited 배열에 pop한 node 방문 처리
# pop한 정점과 인접하지만 방문 안한 정점을 전부 stack에 넣어줌
for v in graph[node]:
if v not in visited:
stack.append(v)
수도코드 (DFS + 재귀 + 인접리스트)
def dfs():
해당 정점 방문 처리
해당 정점(v)과 연결되어있는 정점(i)을 돌면서 (v가 가리키는 연결 리스트 순회)
if i가 방문이 안되어있으면
dfs(i)코드 (DFS + 재귀 + 인접리스트)
def dfs(graph, v, visited):
visited[v] = 1 // 방문 처리
for i in graph[v]: // 방문한 노드와 인접한 다른 노드를 for문으로 돌면서
if visited[i] != 1: // 인접하지만 아직 방문하지 않은 노드에 대해 방문
dfs(graph, i, visited)
BFS
너비 우선 탐색. 큐를 사용해서 구현
최단거리를 구하는 문제에 사용됨
BFS + queue
- 탐색을 시작할 노드를 큐에 넣고 방문 처리
- 큐에서 노드를 dequeue함
dequeue한 노드와 인접한 노드 중 방문 안한 노드 전부를 한번에 큐에 삽입 후 전부 방문 처리
dequeue한 노드와 인접한 노드 전부를 방문했거나 인접한 노드가 없으면 무시 - 큐가 빌 때까지 반복
방문 시점: 큐에 노드를 삽입하기 전
수도코드 (BFS + 재귀 + 인접리스트)
# queue 생성
# visited 배열 생성
시작 정점 queue에 삽입
시작 정점 방문 처리
while (큐가 빌 때까지 반복):
큐에서 정점 하나 뺌
뺀 정점에서 인접한 정점 반복
방문하지 않은 인접한 정점이라면 큐에 넣기
인접한 정점 방문 처리코드 (BFS + 재귀 + 인접리스트)
queue = dequeue()
visited = []
queue.append(start)
visited[start] = 1 # 탐색 시작 노드 방문처리
while queue: # 큐가 빌 때까지 반복
v = queue.popleft()
for i in graph(v):
if (visited[i] != 1):
queue.append(i)
visited[i] = 1문제 1: 음료수 얼려 먹기
위 문제는 얼음틀 형태를 아래와 같이 그래프 형태로 모델링할 수 있음
나와 붙어있고 0인 얼음틀 - 인접한 정점으로 간주
나와 떨어져 있거나 1인 얼음틀 - 인접하지 않은 정점으로 간주
코드 (DFS)
# 행이 n, 열이 m인 2차원 배열 graph에 인접 리스트 형태로 노드 저장되어 있다고 가정
def dfs(x, y):
if x <= -1 or x >= n or y <= -1 or y >= m:
return False # x, y 좌표가 범위를 벗어나는 경우 바로 탐색 중지
if graph[x][y] == 0: # (x, y) 위치에 있는 얼음틀이 0이라면
graph[x][y] = 1 # 해당 노드(얼음틀) 방문 처리 (visited 배열과 graph 같은 걸로 사용)
# 상하좌우에 대해 방문 처리를 하는 이 로직은 return값을 사용하지 않고 방문 처리만 해주기 때문에 result값에 반영이 안됨
dfs(x-1, y) # 상
dfs(x+1, y) # 하
dfs(x, y-1) # 좌
dfs(x, y+1) # 우 방문
return True
return False # graph[x][y]이 0이 아니라면 탐색 종료
result = 0
for i in range(n):
for j in range(m):
# (i, j) 노드를 처음 방문하는 경우에만 result값에 반영됨
if dfs(i, j) == True:
result += 1
print(result)
이중 for문으로 2차원 배열의 모든 칸에서 dfs() 함수를 호출한다
이 때 이미 방문한 경우 두 번째 조건문에 의해 바로 false를 반환하여 탐색이 종료된다 이는 연속된 0이 인접하게 배치되어 있지 않다는 뜻으로 이 때는 result 값에 +1해주면 안된다
재귀 호출을 통해 깊이 우선 방식으로 탐색이 진행되는 경우, 재귀적으로 호출한 함수가 종료되면서 다시 제일 처음 호출한 함수 차례가 되었을 때 두 번째 if문의 return True 문으로 True가 반환된다. 이 경우엔 연속된 0이 인접하게 배치되어 있는 경우란 뜻으로 result 값에 1을 더해주어야 한다.
0이 몇 개 인접해있는지도 구하려면 sum 변수를 파라미터로 넣어주고 정점을 방문할 때마다(두번째 조건문) +1씩 더해준 뒤 반환하면 된다
문제 2: 미로탈출
최단 경로를 구해야 하는 문제기 때문에 BFS를 통해 풀 수 있다
- 시작 지점 (1, 1)에서부터 시작하여 괴물이 없는 1인 노드로만 이동해 (n, m) 노드까지 도달한다
- 정점을 방문할 때마다 해당 정점에 이전 정점까지 온 거리 +1 로 기록해주어 최단 거리를 구한다
코드 (BFS)
# 행이 n, 열이 m인 2차원 배열 graph에 인접 리스트 형태로 노드 저장되어 있다고 가정
# 상, 하, 좌, 우 방향 기록
dx = [-1, +1, 0, o ]
dy = [0, 0, -1, +1]
def bfs(x, y):
queue = deque()
queue.append((x, y)) # 시작 지점 append
while(queue):
x, y = queue.popleft()
# x, y 지점의 상, 하, 좌, 우 위치에 인접한 노드가 있는지 확인
for i in range(4):
nx = x + dx[i]
ny = x + dy[i]
# 미로 공간을 벗어날 경우 무시
if (nx < 0 or nx >=n or ny < 0 or ny >= n):
continue
# 괴물이 있는 곳일 경우 무시
if (graph[nx][ny] == 0):
continue
# 해당 노드를 처음 방문하는 경우에만 최단거리 반영
if (graph[nx][ny] == 1):
graph[nx][ny] = graph[x][y] + 1 # 해당 지점에 이전까지의 최단거리+1 기록함으로써 방문했다고도 표시
queue.append((nx, ny)) # queue에 다시 넣기. 인접한 노드를 한꺼번에 넣으므로 BFS 방식임
return graph[-1][-1]1) 큐를 사용해서 방문한 정점을 관리하고 2) 큐에서 뺀 정점과 인접한 정점 모두를 큐에 삽입, 큐에 삽입 시 방문 처리를 한다는 점에서 BFS임
기타 기억할 점
파이썬에서는 2차원 배열을 통해 그래프를 표현할 나타낼 수 있음
노드가 1번부터 시작하는 경우 graph[0][j]는 비워두고 graph[1][j]부터 1번 노드와 인접한 노드 번호를 넣어둠
python에서 스택 사용 시 그냥 list 자료구조를 사용하면 됨
print(stack[::-1] // top부터 출력
print(stack). // bottom부터 출력python에서 큐 사용 시 deque 라이브러리 사용
from collections import deque
queue = deque()
queue.append(1)
queue.popleft(1)참고:
유튜버 동빛나님 이것이 코딩 테스트다
https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3
https://juhee-maeng.tistory.com/25
학교전공수업
피드백은 언제나 환영입니다!
