BFS와 DFS 문제 유형 및 코드 기본형
코딩 테스트에서 자주 나오는 BFS(Breadth-First Search, 너비 우선 탐색)와 DFS(Depth-First Search, 깊이 우선 탐색) 문제의 유형과 그에 대한 코드 기본형
BFS 문제 유형 예시
- 최단 경로 찾기: 미로 찾기 같은 문제에서 출발점부터 목적지까지 가는 최단 경로를 찾을 때 사용된다.
- 레벨 별 노드 방문: 트리나 그래프에서 같은 레벨에 있는 노드들을 순서대로 방문하고 싶을 때 사용한다.
DFS 문제 유형 예시
- 경로의 존재 여부 확인: 미로 찾기에서 한 지점에서 다른 지점까지 경로가 있는지 없는지를 확인할 때 사용된다.
- 사이클 찾기: 그래프 내에서 사이클(cycle)이 있는지 확인할 때 사용된다.
코드 기본형
BFS 코드 기본형 (Python)
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]:
queue.append(i)
visited[i] = True
graph: 노드 연결 정보를 담고 있는 리스트나 딕셔너리start: 탐색을 시작할 노드visited: 각 노드의 방문 여부를 담고 있는 리스트
DFS 코드 기본형 (Python)
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph: 노드 연결 정보를 담고 있는 리스트나 딕셔너리v: 현재 방문하고 있는 노드visited: 각 노드의 방문 여부를 담고 있는 리스트
