BOJ 28707 - 배열 정렬 링크
(2024.04.19 기준 G1)

문제

길이가 $N$인 양의 정수로 이루어진 배열 $A$가 주어진다. 또한 $M$개의 조작이 주어지는데, 구체적으로 $i$번째 조작은 $l_i$번째 수와 $r_i$번째 수를 바꾸며 비용 $c_i$가 든다. 조작은 순서와 횟수에 상관없이 원하는 대로 할 수 있다.
$A$를 비내림차순으로 정렬하기 위해 필요한 비용 총합의 최솟값 출력

알고리즘

해시 맵을 이용한 다익스트라

풀이

배열의 상태는 최대 $N!$개가 나올 수 있다. 그리고 각 상태마다 다른 상태로 가는 방법이 $M$개이다. 이는 충분히 다익스트라를 이용할 수 있는 범위이다.

각 배열의 상태를 하나의 노드로 생각해서, $A$에서 시작해서 $M$개의 조작마다 나오는 상태로 다익스트라를 진행하면 된다. 이때, 배열의 상태 자체를 노드로 생각해서 $dist$ 배열을 해시 맵과 같은 자료구조로 사용하면 된다.

그리고 마지막엔 정렬된 $A$가 $dist$ 배열에 담겨 있는지(다익스트라를 진행할 때 도달했는지)로 판별하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, vector<int>> piv;

struct Query{
    int l, r, c;
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    vector<int> A(N); for (int i = 0; i < N; i++) cin >> A[i];

    int M; cin >> M;
    vector<Query> Q(M); for (int i = 0; i < M; i++) cin >> Q[i].l >> Q[i].r >> Q[i].c;

    priority_queue<piv, vector<piv>, greater<piv>> pq; pq.push({0, A});
    map<vector<int>, int> dist; // 배열이 키인 맵을 dist 배열로 사용한다.
    dist[A] = 0;

    // 다익스트라
    while (!pq.empty()){
        auto [cost, now] = pq.top(); pq.pop();
        if (dist[now] < cost) continue;
        for (auto [l, r, c]: Q){
            swap(now[l - 1], now[r - 1]); // 조작 결과
            if (dist.find(now) == dist.end() || dist[now] > cost + c){ // 조작 결과인 키가 dist에 있는지부터 확인한다.
                dist[now] = cost + c;
                pq.push({cost + c, now});
            }
            swap(now[l - 1], now[r - 1]); // 조작 전으로 되돌리기;
        }
    }

    // 주어진 배열을 정렬한 다음, 결과가 저장되어 있는지 확인한다.
    sort(A.begin(), A.end());
    if (dist.find(A) == dist.end()) cout << -1;
    else cout << dist[A];
}

• Python

import sys; input = sys.stdin.readline
from heapq import heappop, heappush

N = int(input())

# 주어지는 배열을 하나의 노드로 이용하기 위해 문자열로 만들어준다.
A = ''
for c in input().split():
    A += str(int(c) - 1)

M = int(input())
Q = [tuple(map(int, input().split())) for _ in range(M)]

pq = [(0, A)]
dist = dict() # 문자열이 키인 맵을 dist 배열로 사용한다.
dist[A] = 0

# 다익스트라
while pq:
    cost, now = heappop(pq)
    if dist[now] < cost:
        continue
    for l, r, c in Q:
        nxt = now[:l - 1] + now[r - 1] + now[l:r - 1] + now[l - 1] + now[r:] # 조작 결과
        if nxt not in dist or dist[nxt] > cost + c: # 조작 결과인 키가 dist에 있는지부터 확인한다.
            dist[nxt] = cost + c
            heappush(pq, (cost + c, nxt))

# 주어진 배열을 정렬한 다음, 결과가 저장되어 있는지 확인한다.
A = ''.join(sorted(A))
if A not in dist:
    print(-1)
else:
    print(dist[A])