[BOJ] 28707 - 배열 정렬

https://www.acmicpc.net/problem/28707

BOJ - 배열 정렬

문제 유형: 문자열 처리, 최단 경로, 다익스트라, 해시

문제 난이도: Gold I

시간 제한: 1초

메모리 제한: 1024MB

 

문제

길이가 N인 양의 정수로 이루어진 배열 A=[A1,A2,⋯,AN]이 주어집니다. 이 배열을 비내림차순, 즉, A1≤A2≤⋯≤AN이 되도록 정렬하기 위해서 다음과 같은 M가지 조작을 순서와 횟수에 상관 없이 원하는 만큼 할 수 있습니다.

•  A의 li번째 수와 ri번째 수를 바꿉니다. 비용은 ci가 듭니다. (1≤i≤M)

 A를 비내림차순으로 정렬하기 위해 필요한 비용 총합의 최솟값을 출력하세요.

 

입력

첫 줄에 배열 A의 길이 N이 주어집니다. (2≤N≤8)

둘째 줄에 A의 각 원소 A1,⋯,AN이 공백으로 구분되어 주어집니다. (1≤Ai≤10)

셋째 줄에 조작의 개수 M이 주어집니다. (1≤M≤10)

다음 M개의 줄의 i번째 줄에 조작을 의미하는 세 개의 정수 li,ri,ci가 공백으로 구분되어 주어집니다. (1≤li<ri≤N; 1≤ci≤10)

 

출력

첫 줄에 배열 A를 비내림차순으로 정렬하기 위해 필요한 비용 총합의 최솟값을 출력하세요. 단, 배열을 비내림차순으로 만드는 것이 불가능한 경우 대신 −1을 출력하세요.

 

풀이

숫자가 1 ~ 10이므로, 1씩 빼주면 0~9로 표현이 가능하다. 즉, 상태를 numeric 문자열로 표현가능하다.

입력받을 때 1씩 뺀 숫자들을 붙여서 문자열 상태로 만든다. 초기 문자열이 초기 상태이다.

거리를 저장하기 위해, 해시 맵에 string을 키로 하는 최소비용을 저장할 것이다.

 

스왑 연산 정보도 1-indexed에서 0-indexed로 변환해서 가능한 이동의 경우들을 담는 배열에 저장해놓는다.

 

최소 힙 우선순위 큐를 만들어서 {0, 초기상태}를 넣고 시작한다.

각 가능한 모든 연산을 적용하여 처음 방문한 상태이거나 기존 방문한 상태보다 더 저렴한 경우, 우선순위 큐에 비용을 업데이트해서 넣는다.

즉, 다익스트라를 한다고 보면 된다.

 

최종적인 정답은 해시 맵에 문자열의 정렬된 버전을 키로 넣어서 값을 얻으면  되는데, 만약 없다면 -1을 출력하고, 아니라면 해시맵에 정렬된 문자열을 키로 하는 값을 출력해주면 된다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, m;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n;
  string state = "";
  for (int i = 0; i < n; ++i) {
    int temp;
    cin >> temp;
    state += '0' + temp - 1;
  }

  cin >> m;
  vector<tuple<int, int, int>> costs;
  for (int i = 0; i < m; ++i) {
    int l, r, c;
    cin >> l >> r >> c;
    costs.push_back(make_tuple(l - 1, r - 1, c));
  }

  string sorted = state;
  sort(sorted.begin(), sorted.end());
  unordered_map<string, int> mp;
  mp[state] = 0;
  priority_queue<pair<int, string>, vector<pair<int, string>>, greater<>> pq;
  pq.push({0, state});

  while (!pq.empty()) {
    auto current = pq.top();
    int cost = current.first;
    string curState = current.second;
    pq.pop();

    if (cost > mp[curState])
      continue;
    for (int i = 0; i < m; ++i) {
      auto &[l, r, c] = costs[i];
      string next = curState;
      swap(next[l], next[r]);
      if (mp.find(next) == mp.end() || cost + c < mp[next]) {
        mp[next] = cost + c;
        pq.push({mp[next], next});
      }
    }
  }

  if (mp.find(sorted) == mp.end())
    cout << "-1\n";
  else
    cout << mp[sorted] << "\n";

  return 0;
}