Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 2D 데카르트 좌표점들을 모두 연결하는 최소 비용 구하기

2차원 데카르트 좌표 평면 위에 점(x, y)들의 목록이 주어져 있다고 가정해 봅시다. 두 점 (x0, y0)과 (x1, y1)을 연결할 때 드는 비용은 맨해튼 거리인 |x0 - x1| + |y0 - y1|로 정의됩니다. 임의의 개수만큼 점을 연결할 수 있을 때, 모든 점이 하나의 경로로 연결되도록 만드는 최소 비용을 구하는 것이 이번 문제의 목표입니다.

예를 들어 입력이 다음과 같다고 해보겠습니다.

points = [[0, 0], [0, 2], [0, -2], [2, 0], [-2, 0], [2, 3], [2, -3]]

C++로 2D 데카르트 좌표점들을 모두 연결하는 최소 비용 구하기

이 경우 출력은 14가 됩니다. 그 이유는 다음과 같습니다.

  • 원점 (0, 0)에서 (0, 2), (0, -2), (2, 0), (-2, 0)까지의 연결 비용은 각각 2이므로 총 8
  • (2, 3)은 (0, 2)와 가장 가까우며, 비용은 |2 - 0| + |3 - 2| = 3
  • (2, -3)은 (0, -2)와 가장 가까우며, 비용 역시 3

따라서 총 비용은 8 + 6 = 14입니다.

문제의 본질: 최소 신장 트리(MST)

이 문제는 사실 최소 신장 트리(Minimum Spanning Tree) 문제입니다. 각 좌표점을 노드로, 두 점 사이의 맨해튼 거리를 간선의 가중치로 생각하면, MST를 구성하는 간선 가중치의 합이 곧 최소 연결 비용이 됩니다. 여기서는 대표적인 MST 알고리즘인 프림(Prim) 알고리즘을 활용해 해결합니다.

풀이 접근 방법

  • MAX는 무한대를 의미하는 충분히 큰 값으로 설정합니다.
  • interval(i, j, p): 점 i와 점 j 사이의 맨해튼 거리를 반환하는 함수입니다.
  • 메인 함수(solve)의 동작 순서는 다음과 같습니다.
    • n := 점의 개수
    • n < 2이면 연결이 필요 없으므로 0을 반환
    • distance 배열을 n개 크기로 선언하고 MAX로 초기화
    • visited 배열을 생성하여 방문 여부를 관리
    • distance[0] := 0 으로 시작점 설정
    • i를 0부터 n-1까지 반복하며:
      • 방문하지 않은 노드 중 distance 값이 가장 작은 노드를 선택
      • 선택한 노드를 방문 처리하고, cost에 해당 distance 값을 더함
      • 아직 방문하지 않은 나머지 노드들에 대해, 새로 선택된 노드를 거쳐가는 거리가 기존 값보다 짧으면 distance를 갱신
    • 모든 반복이 끝나면 cost를 반환

예제 코드

아래 C++ 구현을 통해 더 자세히 이해해 보겠습니다.

#include <iostream>
#include <vector>
#define MAX 99999
using namespace std;

int interval(int i, int j, vector<vector<int>>& p) {
    return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]);
}

int solve(vector<vector<int>>& p) {
    int n = p.size(), cost = 0;
    if (n < 2) return 0;

    vector<int> distance(n, MAX);
    vector<bool> visited(n);

    distance[0] = 0;

    for (int i = 0; i < n; i++) {
        int min_d = MAX, node = 0;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && distance[j] < min_d) {
                min_d = distance[j];
                node = j;
            }
        }

        visited[node] = true;
        cost += distance[node];

        for (int j = 0; j < n; j++) {
            if (!visited[j]) {
                int d = interval(node, j, p);
                distance[j] = min(distance[j], d);
            }
        }
    }
    return cost;
}

int main(){
    vector<vector<int>> points = {{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}};
    cout << solve(points);
}

입력

{{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}

출력

14

복잡도 분석

위 구현은 인접 행렬 방식의 프림 알고리즘으로, 시간 복잡도는 O(n²)입니다. 점의 개수 n이 수천 개 수준이라면 충분히 실용적이며, 우선순위 큐(힙)를 활용하면 희소 그래프 형태로 변환하여 O(E log V)로 개선할 수도 있습니다.