BFS / DFS
[참고 사이트]
https://blog.encrypted.gg/1016
https://suyeon96.tistory.com/32
BFS(너비우선 탐색)(거리)
특정 노드에서 시작하여 인접한 노드를 먼저 탐색해 나가는 방법.(가까운 정점부터)
작동 순서(큐 사용)
- 시작하는 정점을 큐에 넣고 방문했다는 표시 남김
- 큐에서 정점을 꺼내서 그 정점과 연결된 모든 정점들에 대해 3번 진행
- 해당 정점을 이전에 방문했다면 아무 것도 하지 않고, 처음 방문했으면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
- 큐가 빌 때까지 2번을 반복합니다.
모든 정점이 큐에 최대 1번씩 들어가므로 인접 행렬에서 O(V^2), 인접 리스트에서 O(V+E)시간 복잡도 존재
특징
- 단계별 탐색: 가까운 정점을 먼저 방문, 인접한 정점 방문
- 탐색 순서 기록: 각 정점이 방문되는 순서가 레벨별로 수행
- 큐 사용: 방문할 정점을 큐에 저장하여 처리
- 시간 복잡도: 일반적으로 O(V+E)이다.
- 최단 경로: 시작 정점에서 다른 정점까지 최단 경로를 찾을 때 사용
밑의 코드는 슈도코드와 파이썬을 결합한 BFS 코드이다.(김윤호님 작성)
BFS(G, s)
for each_Node u ∈ G.V -{s}
## 초기화 코드
u.color = WHITE
u.d = ∞
u.π = null
s.color = GRAY
s.d = 0
s.π = NULL
## 회색 친구들 저장소
Q = []
Q.insert(s)
while len(Q) != 0 ## 종료 조건으로 모든 정점이 발견 되어서 종료시켜도 됨
u = Q.pop()
## 배열에 저장되어져 있는 친구들 전부다 확인
## 여기서 원하는 조건 찾으면 종료해도 됨, 하지만, BFS는 전체탐색의 의의도 있으니 아닌 경우도 많음
for G.adj[u] 에 있는 각 정점 v
if v.color == WHITE
v.color = GRAY ## 탐색 기준의 대상
v.d = u.d+1 ## 대상의 거리는 지금 거리보다 1 큼
v.π = u ## 그친구의 부모노드는 나다
Q.insert(s)
u.color = BLACKDFS(타임 스탬프)
특정 노드에서 시작하여 다음 가지로 넘어가기 전에 해당 분기를 완벽하게 탐색함. 모든 정점을 방문
작동 순서(스택 사용)
- 시작하는 정점을 스택에 넣고 방문했다는 표시를 남김
- 스택에서 정점을 꺼내서 그 정점과 연결된 모든 정점들에 대해 3번을 수행
- 해당 정점을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기로 해당 칸을 스택에 삽입
- 스택이 빌 때 까지 2번 반복
BFS와 같이 모든 정점이 스택에 최대 1번씩 들어가므로 인접 리스트에서 O(V+E), 인접 행렬에서 O(V^2)의 시간 복잡도 존재
특징
- 깊이 우선 탐색: 가능한 한 깊게 탐색하고, 더 이상 탐색할 곳이 없으면 이전 정점으로 돌아가 다음 경로를 탐색
- 스택(Stack) 또는 재귀 사용: 보통 스택이나 재귀를 사용하여 구현
- 백트래킹: 문제 해결을 위한 경로를 찾을 때 유용, 해가 없는 루트는 즉시 포기하고 다시 이전 단계로 돌아감
- 시간 복잡도: 일반적으로 O(V + E)
- 발견 시간과 종료 시간은 괄호 구조를 가진다(종료가 되야한다)(타임스탬프)
밑의 코드는 슈도코드와 파이썬을 결합한 DFS 코드이다.(김윤호님 작성)
DFS(G)
for each_Node u ∈ G.V -{s}
## 초기화 코드
u.color = WHITE
u.π = null
time = 0
for each_Node u ∈ G.V -{s}
if u.color = WHITE
DFS-VISIT(G, u)
DFS-VISIT(G, u)
time = time + 1 ## 흰색 정점에 u가 발견되면 시간을 업데이트 후
u.d = time ## 저장
u.color = Gray
for G.adj[u] 에 있는 각 정점 v ## 각 간선(u, v)을 탐색
if v.color == WHITE
v.π = u
DFS-VISIT(G, v)
time = time + 1
u.f = time
u.color = BLACK ## 끝나면 검정색이용BFS와 DFS의 장단점
파이썬에서는 BFS와 DFS를 라이브러리를 활용하여 쉽게 구현가능합니다.
구현과 관련된 정보는 https://velog.io/@tks7205/dfs%EC%99%80-bfs%EB%A5%BC-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-%EC%97%AC%EB%9F%AC%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95-in-python 해당 블로그를 참조해보자.
+ [추가사항] 코드내용 추가
DFS와 BFS에 대해 행렬을 통한 방법과 DFS 스택을 사용한 코드를 추가
기존에 나는 행렬을 사용해서 False와 True를 체크해 DFS를 구현했다. 1260 백준 문제 답
import sys
def dfs(idx) :
global visited # 방문기록을 지역변수로 불러옴
visited[idx] = True # 정점의 방문기록 True
print(idx, end = ' ') # 정점을 출력
for next in range(1, N+1) : # 인덱스 1부터 끝까지 순회하며 확인
if not visited[next] and graph[idx][next]: # 방문하지 않았고 간선이 존재하는 정점이라면
dfs(next) # dfs에 재귀적으로 입력
def bfs():
global q, visited # 방문기록, 큐를 지역변수로 불러옴
while q: # 큐가 빌때까지 실행
cur = q.pop(0) # 현재 큐 중에 맨 앞 큐를 pop한 것을 cur에 저장
visited[cur] = True # 방문을 True로 바꿈
print(cur, end = ' ') # cur을 차례대로 출력
for next in range(1, N + 1) : # 인덱스 1부터 끝까지 순회하며 확인
if not visited[next] and graph[cur][next]: # 방문하지 않았고 간선이 존재하는 정점이라면
visited[next] = True # 다음 방문할 곳을 방문했다고 표시
q.append(next) # 다음 방문지를 큐에 저장
# 0. 입력 및 초기화
input = sys.stdin.readline
N, M, V = map(int, input().split()) # 입력값 받음
# N은 정점의 총 개수, M은 간선의 총 개수, V는 첫 정점
graph = [[False] * (N + 1) for _ in range(N + 1)] # 그래프를 N*N만큼 2차원 배열로 표현(초기는 모두 Flase)
visited = [False] * (N + 1) # 방문자도 N만큼 Flase로 지정
# 1. graph 정보 입력
for _ in range(M) :
a, b = map(int, input().split())
graph[a][b] = True # 입력된 좌표는 갈 수 있음을 표시
graph[b][a] = True # 입력된 좌표는 갈 수 있음을 표시
# 2. dfs
dfs(V)
print()
# 3. bfs
visited = [False] * (N + 1) # 방문자도 N만큼 Flase로 지정
q = [V] # Q에 초깃값 입력
bfs()초장에는 직관적이고 쉬웠다. 물론 스택 구현을 아예 모르는건 아닌데, 자세하게는 몰라서 알아보기로 했다.
다음은 스택과 리스트를 활용한 DFS 코드이다.
# 스택과 방문 기록을 따로 관리
stack, visited = list(), list()
# 시작 노드를 스택에 지정
stack.append(start_node)
# 스택 소진시까지 진행, 즉 방문이 필요한 곳이 없을 때까지 진행
while stack:
# 그 중에서 가장 마지막 데이터를 추출 (스택 pop)
node = stack.pop()
# 만약 그 노드가 방문한 목록에 없다면
if node not in visited:
# 방문한 목록에 추가
visited.append(node)
# 현재 노드와 연결된 모든 노드들을 스택에 추가( '1':['3', '2'] 형식)
stack.extend(graph[node])
return visited행렬로 풀었을 때와 달리 지금은 스택이 이해가 더 잘되는 것 같다. 코드도 간단하다.
