백준 28707 - 배열 정렬 (C++)

문제

• 문제 링크

  
   BOJ 28707 - 배열 정렬 
  

• 문제 요약

길이가 $N$인 배열 $A = [A_1, A_2, ... A_N]$와 $M$가지의 조작 정보가 주어진다.
조작을 순서, 횟수에 상관없이 원하는만큼 적용할 수 있을 때, $A$가 비내림차순이 되도록 하는 데에 드는 최소 비용을 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$2 ≤ N ≤ 8$

$1 ≤ M, A_i,c_i ≤ 10$

알고리즘 분류

• 자료 구조 (data_structures)
• 그래프 이론 (graphs)
• 트리를 사용한 집합과 맵 (tree _ set / map)
• 다익스트라 (dijkstra)

풀이

오랜만에 참신한 문제를 만났다.

범위가 굉장한 힌트를 주지만 뭔가 구현이 답답할 수 있는데, 한 번 이렇게 생각해보자.

어떤 한 순간의 배열 상태를 노드로 둬보자.

이에 따라 임의의 조작은 한 노드에서 다른 노드로 향하는 간선이 된다.

그럼 문제는 그래프에서의 최단 거리를 묻는 기본적인 것으로 바뀌고,

가중치가 존재하므로 다익스트라를 이용해 풀 수 있게 된다.

시작 노드에서 어떤 노드까지의 $dist$는 $map$ 자료 구조를 이용해 필요한 만큼만 공간을 만들어 줄 수 있다.

최종적으로 $map$에 정렬된 $A$가 존재하는지 확인해보면 되겠다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int n; cin >> n;
 
    vector <int> A(n);
    for (int& i : A) cin >> i;
 
    int m; cin >> m;
 
    vector <tuple <int, int, int>> M(m);
    for (auto& [l, r, c] : M)
    {
        cin >> l >> r >> c;
        l--, r--;
    }
 
    priority_queue <pair<int, vector <int>>> pq;
    map <vector <int>, int> dist;
 
    for (pq.push({ dist[A] = 0, A }); pq.size();)
    {
        auto [cost, now](pq.top()); pq.pop();
        if (dist[now] >= -cost)
            for (auto& [l, r, c] : M)
            {
                swap(now[l], now[r]);
                if (!dist.count(now) || dist[now] > c - cost)
                    pq.push({ -(dist[now] = c - cost), now });
                swap(now[l], now[r]);
            }
    }
 
    sort(A.begin(), A.end());
    cout << (dist.count(A) ? dist[A] : -1);
}

comment

끝