순열의 사이클 분해와 첫 원소 선택 여부로 나누는 최소 비용 DP

원형으로 연결된 원소에서 이웃한 두 원소 중 적어도 하나를 골라야 한다면, 선형 DP를 그대로 적용하기 어렵다. 마지막 원소와 첫 원소도 이웃하기 때문이다. 중간까지의 선택이 올바르더라도 원을 닫는 순간 조건을 어길 수 있다.

27531.cpp의 핵심은 연결 관계를 사이클로 분리하고, 각 사이클에서 첫 원소를 고르는 경우와 고르지 않는 경우를 따로 계산하는 것이다. 첫 원소의 상태를 고정하면 마지막 원소의 선택 조건도 정해진다.

코드가 계산하려는 값은 각 연결의 양 끝 중 적어도 하나를 선택하는 최소 비용으로 해석할 수 있다. 다만 이 해석과 구현이 맞아떨어지려면 입력의 연결이 서로 독립적인 사이클을 이루어야 한다. 먼저 그 전제부터 살펴보는 편이 좋다.

순열이면 연결을 사이클로 나눌 수 있다

입력 (a, b, p)는 a에서 b로 이어지는 연결과 a의 선택 비용 p로 저장한다. 처음에는 세 값을 중첩된 pair에 함께 넣었지만, 이후 연결과 비용을 분리했다.

vector<pii> ab(N + 1);
map<int, int> cost;

int a, b, p;
for (int i = 1; i <= N; i++) {
    cin >> a >> b >> p;
    ab[i] = {a, b};
    cost[a] = p;
}

sort(ab.begin() + 1, ab.end());

정렬 뒤에는 ab[u].second를 정점 u의 다음 정점으로 사용한다. 이를 위해서는 첫 번째 값 a가 1부터 전체 입력 크기까지 한 번씩 등장해야 한다. 그래야 정렬된 ab[u].first가 정확히 u가 된다. 정렬만으로 임의의 정점 번호를 배열 인덱스로 바꿀 수 있는 것은 아니다.

두 번째 값 b도 같은 범위의 순열이면 각 정점의 나가는 연결과 들어오는 연결이 모두 하나이다. 따라서 어느 정점에서 출발하든 연결을 따라가면 출발점으로 돌아오고, 전체 정점은 겹치지 않는 사이클들로 나뉜다.

구현은 방문하지 않은 정점에서 출발해 다음 정점을 반복해서 따라간다.

for (int i = 1; i <= N; i++) {
    if (vst[i]) continue;
    cycles.push_back(vector<pii>());
    cycles.back().push_back({0, 0});  // 1-based;

    int u = i;
    while (!vst[u]) {
        cycles.back().push_back(ab[u]);
        vst[u] = true;
        u = ab[u].second;
    }
}

각 사이클의 0번 칸에는 더미를 넣었다. 실제 원소는 c[1]부터 시작하고, 사이클 길이는 c.size() - 1이다. 사이클 안의 위치 i와 원래 정점 번호는 다르므로 비용은 cost[i]가 아니라 cost[c[i].first]로 가져온다.

이 분해는 일반적인 함수 그래프에는 그대로 적용할 수 없다. 다음 정점만 하나이고 들어오는 연결은 여러 개일 수 있다면, 새 경로가 이미 방문한 경로로 합류할 수 있다. 그때 수집한 정점 목록은 하나의 사이클이 아니다. 이 코드에서 순열이라는 전제는 단순한 편의가 아니라 알고리즘의 기반이다.

선형 DP: 선택한 원소 사이에 빈칸은 하나까지만

사이클 하나의 길이를 L, 각 위치의 비용을 w[i] = cost[c[i].first]라고 하자. 모든 이웃 쌍에서 적어도 하나를 골라야 한다는 조건은, 고르지 않은 원소 두 개가 연속할 수 없다는 뜻이다.

먼저 원형의 마지막 연결을 제외하고 생각한다. D[i]를 다음과 같이 정의한다.

첫 위치의 선택 조건을 고정한 상태에서, 1번부터 i번까지의 이웃 조건을 만족하고 i번을 선택하는 최소 비용이다.

현재 i를 선택한다면 바로 앞의 선택 위치는 i-1 또는 i-2이다. 그보다 멀리 떨어져 있으면 선택하지 않은 두 원소가 연속하게 된다. 따라서 전이는 다음과 같다.

D[i] = min(D[i-1], D[i-2]) + w[i]

예를 들어 i-2를 고른 상태에서 i를 고르면, 그 사이의 i-1은 건너뛰어도 된다. 양쪽 연결을 각각 i-2와 i가 담당하기 때문이다.

중요한 점은 이 상태가 단순히 “i번까지의 최솟값”이 아니라 i번을 반드시 선택한 최솟값이라는 것이다. 이 의미를 유지해야 초기값과 마지막 처리를 설명할 수 있다.

첫 원소를 고정하면 원을 닫을 수 있다

최종 코드의 dp1은 첫 원소를 선택한 경우, dp2는 선택하지 않은 경우를 계산한다. 길이 1인 경우를 제외한 초기값은 다음과 같다.

dp1[1] = cost[c[1].first];
dp1[2] = dp1[1] + cost[c[2].first];

dp2[1] = INF;
dp2[2] = cost[c[2].first];

dp1[2]는 첫 원소와 두 번째 원소를 모두 고른 비용이다. 상태 자체가 현재 원소를 선택하도록 정의되어 있기 때문이다.

반면 첫 원소를 고르지 않았다면 두 번째 원소는 반드시 골라야 한다. 따라서 dp2[2]는 두 번째 원소의 비용만 가진다. dp2[1]은 “첫 원소를 고르지 않았지만 첫 원소를 선택한 상태”이므로 불가능을 나타내는 INF이다.

이 초기화는 수정 과정에서 중요한 부분이었다. dp2[1]은 처음 INF로 작성되었다가 한때 0으로 바뀌었고, 다시 INF로 돌아왔다. 그런데 당시 dp2[2]에는 여전히 dp2[1] + w[2]가 들어가 있었다. 그러면 가능한 시작 상태인 두 번째 원소 선택에도 불가능 상태의 비용이 붙는다. 이후 이를 w[2]만 넣는 형태로 고쳤다.

중간 위치는 두 배열에 같은 점화식을 적용한다. 최종 코드에서 반복문 안의 N은 전체 입력 크기가 아니라 현재 사이클의 길이이다.

for (int i = 3; i < N; i++) {
    dp1[i] = min(dp1[i - 1], dp1[i - 2]) + cost[c[i].first];
    dp2[i] = min(dp2[i - 1], dp2[i - 2]) + cost[c[i].first];
}

dp1[N] = min(dp1[N - 1], dp1[N - 2] + cost[c[N].first]);
dp2[N] = min(dp2[N - 1], dp2[N - 2]) + cost[c[N].first];

마지막 위치에서는 두 경우의 조건이 달라진다.

첫 원소를 골랐다면 마지막 원소를 건너뛸 수 있다. 이때는 마지막 직전 원소를 골라야 하므로 dp1[L-1]이 후보이다. 마지막 원소를 고르는 후보로는 dp1[L-2] + w[L]을 사용한다. 일반적으로 dp1[L-1] + w[L]도 생각할 수 있지만, 비용이 음수가 아니라면 이미 후보인 dp1[L-1]보다 나을 수 없어 생략할 수 있다. 이 마지막 대입 이후의 dp1[L]은 L번 선택을 강제하는 중간 상태와 달리, 첫 원소를 고른 경우의 완성된 답이다.

첫 원소를 고르지 않았다면 마지막 원소는 반드시 골라야 한다. 그래야 마지막과 첫 번째를 잇는 연결을 만족한다. 따라서 dp2는 마지막에도 현재 원소의 비용을 더하는 전이를 그대로 사용한다.

길이가 3 이상인 사이클에서는 이렇게 두 경우가 모든 유효한 선택을 나누어 담당한다. 예를 들어 비용이 [4, 2, 7, 3]인 사이클이라면 첫 원소를 건너뛰고 두 번째와 네 번째를 골라 비용 5로 모든 연결을 만족시킬 수 있다.

더미 칸과 짧은 사이클의 경계

DP를 처음 작성할 때는 전체 입력 크기 N을 각 사이클의 반복문과 마지막 처리에 사용했다. 사이클이 여러 개라면 개별 배열의 길이와 맞지 않는 경계이다.

이후 DP 배열 크기와 답을 읽는 위치를 조정하고, 반복 범위를 사이클 크기로 바꿨다. 사이클 내부의 지역 변수도 처음에는 N = c.size()였지만, 이 값에는 더미 칸이 포함되어 있었다. 최종적으로 N = c.size() - 1로 바꾸면서 실제 마지막 원소의 인덱스와 일치시켰다.

마지막 수정은 길이 1의 별도 처리이다.

int N = c.size() - 1;
if (N == 1) {
    ans += cost[c[1].first];
    continue;
}

자기 자신으로 돌아오는 연결을 만족하려면 그 원소를 선택해야 한다는 해석이다. 동시에 뒤의 초기화에서 존재하지 않는 c[2]에 접근하는 것도 막는다.

길이 2에서는 한 원소만 골라도 두 정점을 잇는 연결을 모두 만족한다. 최종 코드는 벡터의 0번 칸이 0으로 초기화되는 성질을 통해 dp1[2] = min(w[1], w[2]), dp2[2] = w[2]를 계산하므로 최종 결과는 두 비용의 최솟값이다. 다만 이 경우 마지막의 dp1[2]는 “첫 원소를 골랐다”는 이름과 엄밀히 일치하지 않는다. 코드를 더 명료하게 정리한다면 길이 2도 별도로 처리할 수 있지만, 이는 기록된 수정이 아니라 추가 개선 방향이다.

서로 다른 사이클 사이에는 연결이 없으므로 각 사이클의 최솟값을 독립적으로 구해 더하면 된다.

복잡도와 남아 있는 수치 범위 문제

전체 정점 수를 M이라고 하면 정렬에 O(M log M)이 든다. 사이클 탐색은 각 정점을 한 번 방문하고 DP 상태 수도 전체 O(M)개이다. 다만 비용을 map에서 조회하므로 현재 구현의 전체 시간 복잡도는 O(M log M), 공간 복잡도는 O(M)이다.

수치 범위는 별도로 주의해야 한다. 최종 코드는 비용과 DP, 정답을 모두 int로 저장하고 INF를 3e8로 둔다. 비용이 음수가 아니어야 앞서 설명한 마지막 후보 생략이 성립하며, 합계와 중간 계산도 자료형 범위 안에 있어야 한다.

특히 INF가 충분히 크지 않으면 불가능한 상태가 실제 최솟값으로 선택될 수 있다. 예를 들어 길이 3인 사이클의 비용이 [400000000, 400000000, 1]이라면 필요한 최소 비용은 400000001이다. 하지만 현재 dp2의 마지막 식은 min(400000000, 300000000) + 1을 계산해 300000001을 후보로 만든다. 이는 두 번째 원소도 고르지 않은 불가능한 경로의 비용이다.

따라서 입력 범위에 맞춰 자료형과 INF를 정하고, INF에 비용을 더하는 연산까지 안전하게 다뤄야 한다. 이 구현에서 경계란 배열의 마지막 칸만을 뜻하지 않는다. 원을 닫는 선택 조건과 불가능한 상태의 수치 표현까지 맞아야 사이클 DP가 완성된다.