DFS와 BFS 그리고 재귀함수 진입장벽이 좀 느껴진다. 제공된 문제들이 개념 숙지도 안된 상태에서 풀기에는 너무 어려워서 기본 개념을 위주로 학습했다.
DFS와 BFS의 차이는 크게 재귀함수를 사용하는 것과 덱을 활용하는 것 같다. 최단거리와 같은 조건이 있을 때는 여러 조건을 한차례씩 접근하는 BFS을 사용해야 하는 정도가 다른 점인듯하다. 같은 팀에서 문제풀이에 설명을 적극적으로 해주는 팀원분이 BFS가 더 직관적으로 느껴져서 BFS을 우선으로 풀이하는 것을 추천해줬다!
더불어 기본 개념을 다질 수 있는 기초 문제들을 추천해줘서 함께 기록한다.
DFS, BFS 기초 문제 추천(백준)
대체로 실버 3~1의 문제들이다. 도전~
백준 1260: DFS, BFS
백준 2606: 바이러스
백준 2468: 안전 영역
백준 2667: 단지번호붙이기
백준 2179: 미로 탐색
DFS와 BFS 개념 잡기
DFS(Depth-First-Search)
- 깊이 우선 탐색으로 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조 또는 재귀 함수를 이용한다.
DFS 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 전부 방문을 했다면 최상단 노드를 스택에서 꺼낸다.
- 위 과정을 방문할 곳이 없을 때까지 반복
DFS 재귀함수로 접근하기
# 그래프 초기 설정
n = int(input())
graph = [[] for _ in range(n+1)]
# 입력값으로 그래프 만들기
for _ in range(int(input())):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
# print(graph) 각 노드가 연결된 정보를 2차원 리스트로 표현
# [
# [], # 노드의 번호가 1번부터면 0번 인덱스는 비우고 씀
# [2, 5], # 1번 인덱스. 1은 2와 5에 갈수있다
# [1, 3, 5],
# [2],
# [7],
# [1, 2, 6],
# [5],
# [4]
# ]
# 각 노드가 방문된 정보를 1차원 리스트로 표현
visited = [False] * (n+1)
# DFS 정의하기
def dfs(graph, v, visited):
visited[v] = True # 현재 노드를 방문 처리
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]: # 1번째 인덱스의 2와 5
if not visited[i]:
dfs(graph, i, visited)
# 정의된 DFS 함수를 호출하기. 1은 시작 노드임
dfs(graph, 1, visited)BFS(Breadth-First Search)
- 너비 우선 탐색으로 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조를 이용한다
BFS 동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼내고 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입함 (한번에)
- 특정 조건에서 최단경로 문제 해결 가능
그림으로 이해하기
DFS로 접근하기
1에서 출발. 1 → 2, 3, 8 가능. 작은 노드를 우선으로 방문해서 2번이 다시 기준점.
스택 [1, 2]
2에서 7로 이동. 스택 [1, 2, 7]
7에서 6으로 이동. 스택 [1, 2, 7, 6] 6에서 더 갈 곳이 없기에 6 를 스택에서 제거.
스택 [1, 2, 7]. 7에서 8로 이동. 스택 [1, 2, 7, 8] 더 갈 곳이 없기에 8 제거.
스택 [1, 2, 7] → [1, 2] → [1] → [1, 3] → [1, 3, 4] → [1, 3, 4, 5]
탐색 순서: 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5
BFS로 접근하기
1번 노드 → 2, 3, 8 가능.
노드1을 꺼내 방문하지 않은 2, 3, 8을 큐에 삽입하고 방문처리
큐에 [2, 3, 8] 있음
노드 2를 꺼내 방문하지 않은 7를 큐에 삽입
큐에 [3, 8, 7] 있음
노드 3를 꺼내서 방문하지 않은 4와 5를 큐에 삽입
큐에 [8, 7, 4, 5] 있음
노드 8 꺼냄. 7 꺼냄. → 큐에 6 넣음 → [4, 5, 6] → 4 꺼냄. 5 꺼냄. 6꺼냄.
탐색 순서(큐에서 꺼낸 순서) 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6
BFS 코드 예제
# 그래프 초기 설정
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(int(input())):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
#print(graph) 각 노드가 연결된 정보를 2차원 리스트로 표현
# [
# [], # 노드의 번호가 1번부터면 0번 인덱스는 비우고 씀
# [2, 5], # 1번 인덱스. 1은 2와 5에 갈수있다
# [1, 3, 5],
# [2],
# [7],
# [1, 2, 6],
# [5],
# [4]
# ]
# 각 노드가 방문된 정보를 1차원 리스트로 표현
visited = [False] * (n+1)
# BFS 정의하기
from collections 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]: # v의 값들이 방문 X라면
queue.append(i)
visited[i] = True
# 정의된 DFS 함수를 호출하기. 1은 시작 노드임
bfs(graph, 1, visited)출처: 나동빈 - 이코테 2021 강의 몰아보기 3.DFS & BFS
(위 유튜브 영상은 DFS, BFS 개념 설명으로 추천!)
