[C++] 배열 정렬 (백준 28707번)

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

 

나는 두가지 방법으로 풀었는데, 공통적으로 필요한 아이디어는 각 배열의 상태를 정점으로 생각하고 하나의 swap 연산을 가중치가 있는 간선으로 생각하는 것이다. 그리고 방문했는지 여부와 걸린 시간은 vector<int> 배열을 key로 하고 걸린 시간 int를 value로 하는 map으로 처리한다. 

 

첫번째는 BFS를 사용한 풀이이다.

단순히 방문할 때마다 비내림차순 상태가 맞는지 확인 후 ans를 갱신하고, 다음 상태들을 쭉 보면서 방문한 적 없거나 시간이 덜 걸린 경우에만 큐에 넣어주면서 탐색했다. 

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

int n, m;
vector<int> a;
vector<int> cura;
vector<tuple<int, int, int>> op;
map<vector<int>, int> vst;
int ans = 500;

bool isAsc() {
    for (int i = 1; i < n; i++) {
        if (cura[i - 1] > cura[i]) return false;
    }
    return true;
}

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

    cin >> n;
    a = vector<int>(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    cin >> m;
    op = vector<tuple<int, int, int>>(m);
    for (int i = 0; i < m; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        op[i] = {l, r, c};
    }

    queue<pair<vector<int>, int>> q;
    q.push({a, 0});
    vst[a] = 0;
    while (!q.empty()) {
        cura = q.front().first;
        int curc = q.front().second;
        q.pop();

        if (isAsc()) ans = min(ans, curc);

        for (int i = 0; i < m; i++) {
            auto [l, r, c] = op[i];
            swap(cura[l - 1], cura[r - 1]);
            if (!vst.count(cura) || curc + c < vst[cura]) {
                vst[cura] = curc + c;
                q.push({cura, curc + c});
            }
            swap(cura[l - 1], cura[r - 1]);
        }
    }

    if (ans == 500) cout << -1 << '\n';
    else cout << ans << '\n';
}

(AC)

맞긴 했지만 시간이 좀 오래 걸리는 것 같아서 찾아보니 정해는 다익스트라 풀이인 것 같았다. 

 

두번째는 다익스트라를 사용한 풀이이다. 

비슷한 방식인데, 그냥 큐 대신 우선순위 큐를 사용하여 걸린 시간이 더 적은 것들 먼저 꺼내서 탐색하는 방식이다. 또한, 매번 내림차순인지 확인하는 것은 비효율적이므로 마지막에 배열 a를 정렬해준 다음에 vst 배열에서 a를 찾아 그 값을 출력하도록 하였다.

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

int n, m;
vector<int> a;
vector<int> cura;
vector<tuple<int, int, int>> op;
map<vector<int>, int> vst;

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

    cin >> n;
    a = vector<int>(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    cin >> m;
    op = vector<tuple<int, int, int>>(m);
    for (int i = 0; i < m; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        op[i] = {l, r, c};
    }

    priority_queue<pair<int, vector<int>>> q;
    q.push({0, a});
    vst[a] = 0;
    while (!q.empty()) {
        int curc = -q.top().first;
        cura = q.top().second;
        q.pop();

        for (int i = 0; i < m; i++) {
            auto [l, r, c] = op[i];
            swap(cura[l - 1], cura[r - 1]);
            if (!vst.count(cura) || curc + c < vst[cura]) {
                vst[cura] = curc + c;
                q.push({-(curc + c), cura});
            }
            swap(cura[l - 1], cura[r - 1]);
        }
    }

    sort(a.begin(), a.end());

    if (vst.count(a)) cout << vst[a] << '\n';
    else cout << -1 << '\n';
}

(AC)