항해99 2주차 - 그래프(DFS/BFS) 이론 정리

Today I learned
2022/01/20

회고록

1/20

항해 99, 알고리즘 1주차

교재 : 파이썬 알고리즘 인터뷰

12장 그래프

1. 이론

DFS와 BFS
DFS와 BFS는 그래프의 탐색 방법
목적: 한 정점에서 시작하여 연결되어 있는 모든 정점을 1번씩 방문

DFS

한 우물을 깊이 파면서 탐색
재귀함수 혹은 스택으로 구현 가능

d_check = [False for _ in range(n + 1)]
def dfs(x):
    d_check[x] = True
    print(x, end = ' ')
    for y in edge[x]:
        if d_check[y] == False:
            dfs(y)

BFS

여러 우물을 동시에 같은 깊이로 탐색
최단 경로 찾기에 사용

from collections import deque
 
def bfs():
    queue = deque([start])
    b_check = [False for _ in range(n + 1)]
    b_check[start] = True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in edge[v]:
            if not b_check[i]:
                b_check[i] = True
                queue.append(i)