[파이썬] 그래프 알고리즘을 활용한 경로 찾기와 최단 거리

04 Sep 2023

python

그래프 알고리즘은 다양한 문제를 해결하는데 사용되는 강력한 도구입니다. 이 중에서도 경로 찾기와 최단 거리 계산은 매우 중요한 문제입니다. 이번 글에서는 이러한 문제를 해결하기 위해 그래프 알고리즘을 활용하는 방법과 파이썬을 사용하여 구현하는 방법을 알아보겠습니다.

그래프 표현

먼저, 그래프를 어떻게 표현할지에 대해 알아보겠습니다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성되어 있으며, 이를 적절히 표현해야 합니다. 파이썬에서는 인접 리스트(Adjacency List)를 사용하여 그래프를 표현하는 것이 일반적입니다.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['C']
}

위 예시에서는 A, B, C, D, E를 정점으로, 각 정점마다 인접한 정점들을 리스트로 표현하였습니다. 이렇게 표현된 그래프에 대해 경로 찾기와 최단 거리 계산을 수행할 수 있습니다.

경로 찾기

경로 찾기는 한 정점에서 다른 정점까지 이동하는 경로를 찾는 문제입니다. 그래프 알고리즘 중 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 가장 널리 사용되는데, 각각의 알고리즘을 사용하여 경로를 찾아보겠습니다.

DFS를 사용한 경로 찾기

DFS는 스택(Stack) 자료구조를 기반으로 동작하는 알고리즘입니다. 아래는 파이썬으로 구현한 DFS로 경로를 찾는 코드 예시입니다.

def dfs(graph, start, end, visited=[], path=[]):
    visited.append(start)
    path.append(start)
    if start == end:
        return path
    for vertex in graph[start]:
        if vertex not in visited:
            new_path = dfs(graph, vertex, end, visited, path)
            if new_path:
                return new_path
    return None

start_vertex = 'A'
end_vertex = 'E'
result = dfs(graph, start_vertex, end_vertex)
print(result)  # 출력: ['A', 'C', 'E']

위 코드에서 dfs() 함수는 현재 정점에서 인접한 정점들을 순회하면서 재귀적으로 호출됩니다. 각 정점을 방문했는지 확인하기 위해 visited 리스트를 사용하고, 경로를 저장하기 위해 path 리스트를 사용합니다. 호출된 함수가 목표 정점을 찾았을 경우에는 path를 반환하여 경로를 출력합니다.

BFS를 사용한 경로 찾기

BFS는 큐(Queue) 자료구조를 기반으로 동작하는 알고리즘으로, 너비 우선으로 탐색하여 경로를 찾습니다. 아래는 파이썬으로 구현한 BFS로 경로를 찾는 코드 예시입니다.

from collections import deque

def bfs(graph, start, end):
    queue = deque([(start, [start])])
    while queue:
        (vertex, path) = queue.popleft()
        if vertex == end:
            return path
        for adjacent_vertex in graph[vertex]:
            if adjacent_vertex not in path:
                queue.append((adjacent_vertex, path + [adjacent_vertex]))
    return None

start_vertex = 'A'
end_vertex = 'E'
result = bfs(graph, start_vertex, end_vertex)
print(result)  # 출력: ['A', 'C', 'E']

위 코드에서 bfs() 함수는 큐를 사용하여 정점과 해당 정점까지의 경로를 함께 저장하며 탐색합니다. 큐에는 현재 정점과 그에 해당하는 경로가 쌍으로 저장되어 있습니다. 각 정점을 방문했는지 확인하기 위해 경로를 사용하고, 경로를 찾았을 경우에는 해당 경로를 반환하여 출력합니다.

최단 거리 계산

최단 거리 계산은 한 정점에서 다른 정점까지의 최단 경로를 찾는 문제입니다. 그래프 알고리즘 중 가장 대표적인 알고리즘은 다익스트라(Dijkstra) 알고리즘입니다. 이를 사용하여 최단 거리를 계산해보겠습니다.

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    heap = [(0, start)]

    while heap:
        (current_distance, current_vertex) = heapq.heappop(heap)

        if current_distance > distances[current_vertex]:
            continue

        for adjacent_vertex, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[adjacent_vertex]:
                distances[adjacent_vertex] = distance
                heapq.heappush(heap, (distance, adjacent_vertex))

    return distances

start_vertex = 'A'
distances = dijkstra(graph, start_vertex)
print(distances)  # 출력: {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2}

위 코드에서 dijkstra() 함수는 distances 딕셔너리를 사용하여 최단 거리를 저장하며 계산합니다. heap 리스트는 (거리, 정점)의 쌍을 저장하고, heappop() 함수를 사용하여 최소 거리를 가진 정점을 꺼내어 탐색합니다. 인접한 정점들에 대해 거리를 갱신하고, 갱신된 거리와 함께 큐에 삽입하여 최단 거리를 계산합니다.

마무리

이번 글에서는 그래프 알고리즘을 활용하여 경로 찾기와 최단 거리 계산을 수행하는 방법을 알아보았습니다. DFS와 BFS를 사용하여 경로를 찾을 수 있고, 다익스트라 알고리즘을 사용하여 최단 거리를 계산할 수 있습니다. 이러한 그래프 알고리즘을 활용하면 다양한 문제에 대해 효율적으로 해결할 수 있습니다. 앞으로 그래프에 관련된 문제를 해결할 때는 이러한 알고리즘을 잘 활용해보세요!