DFS (재귀)

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

DFS (스택)

def dfs_stack(graph, start):
    visited = []
    stack = [start]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            stack.extend(reversed(graph[v]))
    return visited

BFS (큐)

from collections import deque

def bfs(graph, start):
    visited = [start]
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if i not in visited:
                visited.append(i)
                queue.append(i)
    return visited

2차원 BFS (최단거리)

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))