코딩 테스트 대비! 파이썬으로 그래프 탐색 알고리즘(BFS, DFS) 구현하기

파이썬으로 그래프 탐색 알고리즘(BFS, DFS) 구현하기


문제 설명

그래프가 주어졌을 때, 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) 알고리즘을 파이썬으로 구현하라.


예시 입력

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3]
}

솔루션 코드

from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])

    return visited

def dfs(graph, start):
    visited = []
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend(reversed(graph[node]))

    return visited

# 테스트 케이스
print("BFS 결과:", bfs(graph, 1))
print("DFS 결과:", dfs(graph, 1))

코드 설명

이 포스팅에서는 그래프 탐색의 대표적인 두 가지 알고리즘인 BFS와 DFS를 파이썬으로 구현했습니다. 그래프 탐색 알고리즘은 코딩 테스트와 실무에서 다양하게 활용되므로 반드시 학습해야 합니다.


BFS(Breadth-First Search, 너비 우선 탐색) 알고리즘은 시작 노드에서 가까운 노드부터 차례대로 탐색하는 방식입니다. 큐 자료구조를 활용하여 구현할 수 있습니다. 코드에서는 deque 모듈을 이용하여 queue를 생성했습니다. 방문하지 않은 노드를 큐에 넣고, 큐에서 노드를 하나씩 꺼내면서 인접 노드들을 탐색합니다.

DFS(Depth-First Search, 깊이 우선 탐색) 알고리즘은 시작 노드에서 깊이 탐색하다가 더 이상 진행할 수 없으면 다시 되돌아오는 백트래킹 방식입니다. 스택 자료구조를 활용하여 구현할 수 있습니다. 코드에서는 리스트를 스택으로 활용했습니다. 방문하지 않은 노드를 스택에 넣고, 스택에서 노드를 하나씩 꺼내면서 인접 노드들을 탐색합니다.

그래프 문제를 효과적으로 해결하기 위해서는 BFS와 DFS 알고리즘에 대한 이해가 필수적입니다. 각 알고리즘의 장단점을 파악하고, 문제 상황에 맞게 적절히 선택할 수 있어야 합니다. 또한 그래프 표현 방법, 가중치 처리 등 다양한 변형 문제에도 대응할 수 있는 능력이 요구됩니다.