[Python] DFS, BFS

1. DFS

- 깊이 우선 탐색(Depth First Search)

import sys
input = sys.stdin.readline
N, M, v = map(int, input().split())

graph = {}
for i in range(1, N+1):
    graph[i] = []

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dfs_visited = [0] * (N + 1)

def dfs(node):
    dfs_visited[node] = 1
    graph[node].sort()
    for next_node in graph[node]:
        if dfs_visited[next_node] == 0:
            dfs(next_node)

dfs(v)

 

2. BFS

- 너비 우선 탐색(Breadth-First Search)

import sys
input = sys.stdin.readline

N, M, v = map(int, input().split())

bfs_visited = [0] * (N+1)
def bfs(node):
    from collections import deque
    dq = deque([])

    dq.append(node)
    bfs_visited[node] = 1

    while dq:
        now_node = dq.popleft()

        for next_node in graph[now_node]:
            if bfs_visited[next_node] == 0:
                dq.append(next_node)
                bfs_visited[next_node] = 1
                

bfs(v)