문제 개요
n개의 3차원 좌표가 주어져 있다고 가정해 보겠습니다. 좌표 (a, b, c)에서 (x, y, z)로 이동할 때 드는 비용은 다음과 같이 정의됩니다.
|x − a| + |y − b| + max(0, z − c)
우리는 첫 번째 좌표에서 출발하여 나머지 모든 좌표를 최소 한 번씩 방문한 뒤, 다시 첫 번째 좌표로 돌아오는 경로 전체의 총 비용을 계산해야 합니다. 각 좌표는 배열 coords에 담겨 주어집니다.
예를 들어 입력이 n = 3, coords = {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}}라면 출력 결과는 12가 됩니다.
접근 방법: 비트마스크 동적 계획법
이 문제는 사실상 외판원 순회(TSP, Traveling Salesman Problem)의 변형입니다. 좌표의 개수가 작다면 비트마스크(bitmask)를 활용한 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 상태 정의: tpa[i][j]는 "방문한 좌표의 집합이 비트마스크 i이고, 현재 j번째 좌표에 위치할 때의 최소 누적 비용"을 의미합니다.
- 초기 상태: 출발점은 항상 0번 좌표이므로 tpa[1][0] = 0으로 설정합니다(비트마스크 1은 0번 좌표를 방문했음을 뜻함).
- 전이 규칙: 현재 상태 (i, j)에서 아직 방문하지 않은 좌표 t로 이동할 때, 새 상태 (i | (1 << t), t)의 값을 기존 값과 비교하여 더 작은 값으로 갱신합니다.
- 최종 답: 모든 좌표를 방문한 상태(비트마스크 2ⁿ − 1)에 있는 각 좌표에서 다시 0번 좌표로 복귀하는 비용을 더한 값들 중 최솟값을 구합니다.
알고리즘 의사 코드
2차원 배열 tpa를 선언합니다.
tpa[1][0] := 0
i := 1; i < 2^n; i를 1씩 증가하며 반복:
j := 0; j < n; j를 1씩 증가하며 반복:
만약 i mod 2가 0과 같다면:
아래 코드를 건너뛰고 다음 반복으로 진행
t := 0; t < n; t를 1씩 증가하며 반복:
x := coords[t]의 첫 번째 값
y := coords[t]의 두 번째 값
z := coords[t]의 세 번째 값
p := coords[j]의 첫 번째 값
q := coords[j]의 두 번째 값
r := coords[j]의 세 번째 값
tpa[i OR (1을 t만큼 왼쪽 시프트)][t] :=
min(tpa[i | (1 << t)][t],
tpa[i][j] + |x - p| + |y - q| + max(0, z - r))
res := 무한대(INF)
i := 0; i < n; i를 1씩 증가하며 반복:
x := coords[0]의 첫 번째 값
y := coords[0]의 두 번째 값
z := coords[0]의 세 번째 값
p := coords[i]의 첫 번째 값
q := coords[i]의 두 번째 값
r := coords[i]의 세 번째 값
res := min(res, tpa[2^n - 1][i] + |x - p| + |y - q| + max(0, z - r))
return res
여기서 i % 2 == 0인 경우를 건너뛰는 조건은, 출발점인 0번 좌표를 반드시 포함한 상태만 고려하기 위함입니다.
C++ 구현 예시
아래 예제 코드를 통해 실제 구현 방법을 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int solve(int n, vector<tuple<int,int,int>> coords){
vector<vector<int>> tpa(pow(2, n), vector<int>(n, INF));
tpa[1][0] = 0;
for(int i = 1; i < pow(2,n); i++) {
for(int j = 0; j < n; j++){
if(i % 2 == 0)
continue;
for(int t = 0; t < n; t++) {
int x, y, z, p, q, r;
tie(x, y, z) = coords[t];
tie(p, q, r) = coords[j];
tpa[i | (1 << t)][t] = min(tpa[i|(1 << t)][t], tpa[i][j] + abs(x - p) + abs(y - q) + max(0, z - r));
}
}
}
int res = INF;
for(int i = 0; i < n; i++) {
int x, y, z, p, q, r;
tie(x, y, z) = coords[0];
tie(p, q, r) = coords[i];
res = min(res, tpa[pow(2, n) - 1][i] + abs(x - p) + abs(y - q) + max(0, z - r));
}
return res;
}
int main() {
int n = 3;
vector<tuple<int,int,int>> coords = {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}};
cout<< solve(n, coords);
return 0;
}
입력
3, {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}}
출력
12
복잡도 분석
이 알고리즘의 시간 복잡도는 O(2ⁿ × n²), 공간 복잡도는 O(2ⁿ × n)입니다. 따라서 n이 대략 15~20 이하일 때 실용적인 수준으로 동작하며, 좌표 개수가 많아지면 근사 알고리즘이나 휴리스틱 기법을 고려해야 합니다.