[코딩테스트] DFS, BFS 공식

DFS(깊이 우선 탐색)

• 재귀 함수를 이용해 구현
• 시작 노드에서부터 출발해 한 방향으로 최대한 깊게 탐색한 후, 다른 방향의 노드를 탐색
• 스택 또는 재귀 호출을 통해 구현
• 모든 노드를 방문하고자 할 때 사용

def dfs(graph, start, visited=None):
    # 방문한 노드들을 저장할 집합을 초기화
    if visited is None:
        visited = set()
    # 현재 노드를 방문한 것으로 표시하고, 방문한 노드 집합에 추가
    visited.add(start)
    # 현재 노드를 출력
    print(start)  # 방문한 노드 출력
    # 현재 노드의 이웃 노드들을 탐색
    for neighbor in graph[start]:
        # 이웃 노드가 방문한 적이 없다면 재귀적으로 방문
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

BFS(너비 우선 탐색)

• 큐를 이용해 구현
• 시작 노드에서부터 인접한 모든 노드를 탐색한 후, 그 다음 레벨의 노드를 탐색
• 너비(수평)을 우선으로 탐색
• 최단 경로를 찾거나 노드 간의 최단 거리를 구할 때 사용됨. 

from collections import deque

def bfs(graph, start):
    # 방문한 노드들을 저장할 집합을 초기화
    visited = set()
    # 큐를 초기화하고 시작 노드를 추가
    queue = deque([start])
    # 시작 노드를 방문한 것으로 표시
    visited.add(start)
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 노드를 꺼내옴
        vertex = queue.popleft()
        # 꺼낸 노드를 출력
        print(vertex)  # 방문한 노드 출력
        # 꺼낸 노드의 이웃 노드들을 탐색
        for neighbor in graph[vertex]:
            # 이웃 노드가 방문한 적이 없다면 방문 표시하고 큐에 추가
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)