그래프와 최단 거리 문제: MST & TSP

1. Euclidean Distance (유클리드 거리)

두 점 (x1, y1)와 (x2, y2) 사이의 거리를 계산하는 공식이다.

2차원 뿐만 아니라, n차원에서도 같은 원리를 사용한다.

유클리드 거리 공식은 2차원뿐만 아니라, 3차원, 4차원, ..., n차원에서도 동일한 원리로 적용할 수 있다.

• 3차원으로 확장하면?

• n차원에서는?

즉, 차원이 늘어나도 각 좌표의 차이를 제곱한 후 더하고, 루트를 씌우는 원리는 변함없다.

# 2차원에서 유클리드 거리 계산 코드

import math


def euclidean_distance(p1, p2):
    return math.sqrt((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2)


p1 = (1, 2)
p2 = (4, 6)
print(euclidean_distance(p1, p2))  # 5.0

# 4차원에서 유클리드 거리 계산 코드

import math


def euclidean_distance(p1, p2):
    return math.sqrt(sum((a - b) ** 2 for a, b in zip(p1, p2)))


p1 = (1, 2, 3, 4)  # 4차원 좌표
p2 = (4, 6, 7, 8)

print(euclidean_distance(p1, p2))

 

 

 

2. MST(Minimum Spanning Tree, 최소 신장 트리)

• 그래프에서 모든 정점을 포함하면서, 간선 가중치의 합이 최소가 되는 트리이다.
• 사이클이 없고, 모든 노드를 연결하는 최소 비용 네트워크이다.

대표적인 알고리즘으로 2개가 있다.

 

크루스칼 알고리즘(Kruskal's Algorithm)

• 간선을 정렬 후, 유니온 파인드 사용

🌟원리

1. 모든 간선을 가중치 기준으로 정렬
2. 가장 가중치가 작은 간선부터 추가 (사이클이 생기지 않도록)
3. 모든 노드가 연결될 때까지 반복

class DisjointSet:
    """유니온 파인드(Disjoint Set) 자료구조 구현"""
    def __init__(self, n):
        self.parent = list(range(n))  # 각 노드의 부모를 자기 자신으로 초기화

    def find(self, x):
        """루트 노드를 찾는 함수 (경로 압축 적용)"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축
        return self.parent[x]

    def union(self, a, b):
        """두 노드를 같은 집합으로 합치는 함수"""
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a  # 한 쪽을 다른 쪽의 부모로 설정


def kruskal(n, edges):
    """크루스칼 알고리즘으로 MST 구하기"""
    edges.sort(key=lambda x: x[2])  # 간선 리스트를 가중치 기준으로 정렬
    ds = DisjointSet(n)  # 유니온 파인드 자료구조 생성
    mst = []  # MST 간선 리스트

    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):  # 사이클이 생기지 않도록 확인
            ds.union(u, v)  # 두 정점을 합침
            mst.append((u, v, weight))  # MST 추가

    return mst  # 최소 신장 트리 반환


edges = [(0, 1, 1), (1, 2, 3), (0, 2, 2)]  # 그래프 간선(u, v, weight)
print(kruskal(3, edges))  # [(0, 1, 1), (0, 2, 2)]

MST(Minimum Spanning Tree, 최소 신장 트리): 크루스칼 알고리즘

 

 

프림 알고리즘 (Prim's Algorithm) 

• 우선순위 큐(힙) 사용

🌟원리

1. 임의의 정점에서 시작
2. 현재 선택한 정점에서 가장 가중치가 작은 간선 추가
3. 방문하지 않은 정점 중, 가중치가 가장 낮은 간선을 반복적으로 추가 (우선순위 큐 사용 -> 가장 작은 값부터 자동으로 선택됨)

import heapq


def prim(n, graph):
    """프림 알고리즘을 사용해 최소 신장 트리(MST) 찾기"""
    visited = [False] * n  # 방문한 정점을 저장하는 배열
    min_heap = [(0, 0)]  # (가중치, 정점) 형태로 저장하는 우선순위 큐
    mst_cost = 0  # MST 총 비용
    mst_edges = []  # MST 간선 리스트

    while min_heap:
        weight, u = heapq.heappop(min_heap)  # 가장 작은 가중치를 가진 간선 선택
        if visited[u]:  # 이미 방문한 정점이면 스킵
            continue

        visited[u] = True  # 방문 처리
        mst_cost += weight  # MST 비용 누적

        for v, w in graph[u]:  # 현재 정점과 연결된 모든 간선 탐색
            if not visited[v]:  # 방문하지 않은 정점만 추가
                heapq.heappush(min_heap, (w, v))

    return mst_cost  # MST 총 비용 반환


graph = {
    0: [(1, 1), (2, 2)],
    1: [(0, 1), (2, 3)],
    2: [(0, 2), (1, 3)]
}
print(prim(3, graph))  # MST 총 비용 출력

 

 

 

 

3. TSP(Traveling Salesman Problem, 외판원 문제)

한 번만 방문해서 모든 도시를 돌고 최소 비용으로 다시 출발점으로 돌아오는 문제이다.

 

완전 탐색(브루트포스) 풀이

from itertools import permutations


def tsp(graph):
    """모든 순열을 시도하는 완전 탐색 풀이 (O(n!))"""
    n = len(graph)
    min_cost = float('inf')

    for path in permutations(range(n)):  # 모든 경로 순열 생성
        cost = sum(graph[path[i]][path[i + 1]] for i in range(n - 1)) + graph[path[-1]][path[0]]
        min_cost = min(min_cost, cost)  # 최소 비용 갱신

    return min_cost  # 최적 비용 반환


graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
print(tsp(graph))  # 최소 비용 출력

 

 

DP + 비트마스킹 풀이

INF = float('inf')


def tsp_dp(graph):
    """DP + 비트마스킹을 이용한 TSP 풀이"""
    n = len(graph)
    dp = [[None] * (1 << n) for _ in range(n)]  # DP 테이블

    def dfs(curr, visited):
        """현재 도시 curr에서, 방문 상태 visited일 때 최소 비용"""
        if visited == (1 << n) - 1:  # 모든 도시 방문 완료
            return graph[curr][0] or INF  # 다시 시작점(0)으로 돌아가는 비용

        if dp[curr][visited] is not None:  # 이미 계산한 값이면 반환
            return dp[curr][visited]

        min_cost = INF
        for next_city in range(n):  # 모든 도시 탐색
            if visited & (1 << next_city) == 0 and graph[curr][next_city] > 0:
                # 아직 방문 안 한 도시 & 경로가 존재하면 이동
                cost = graph[curr][next_city] + dfs(next_city, visited | (1 << next_city))
                min_cost = min(min_cost, cost)  # 최소 비용 갱신

        dp[curr][visited] = min_cost  # DP 테이블에 저장
        return min_cost

    return dfs(0, 1)  # 0번 도시에서 시작, 0번 도시 방문 상태(0001)


graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

print(tsp_dp(graph))

 

 

 

각 개념에 대해 정리

Euclidean Distance	두 점 사이의 거리 계산	math.sqrt((x2-x1)**2 + (y2-y1)**2)
MST	최소 비용으로 모든 노드 연결	크루스칼 알고리즘 프림 알고리즘
TSP	모든 도시 방문 후 최소 비용 경로 찾기	완전 탐색 DP + 비트마스킹

 

 

 

각 개념의 연관 관계

1. Euclidean Distance -> MST & TSP

• 유클리드 거리는 그래프의 간선 가중치(거리) 계산에 자주 사용된다.
• MST(최소 신장 트리)나 TSP(외판원 문제)에서 도시 간 거리 계산에 활용이 가능하다.

 

2. MST vs TSP (그래프 문제)

• MST(최소 신장 트리) : 그래프에서 최소 비용으로 모든 노드를 연결하는 문제
• TSP(외판원 문제) : 모든 노드를 방문하고 최소 비용으로 다시 출발점으로 돌아오는 문제
• 두 문제 모두 그래프를 기반으로 하지만, MST는 사이클 없이 연결, TSP는 모든 노드를 한 번씩 방문 후 돌아옴(사이클 존재)