[Algorithm] Baekjoon 28707번 : 배열 정렬

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
 
struct Command
{
    int firstIndex;
    int secondIndex;
    int cost;
};
 
struct Node
{
    vector<int> v;
    int cost;
};
 
int n, m;
vector<int> startV;
vector<Command> commands(11);
map<vector<int>, int> dist;
vector<int> target;
const int maxNum = 0x3f3f3f3f;
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.cost > b.cost;
    }
};
 
vector<int> Swap(vector<int> v, int firstIndex, int secondIndex)
{
    int temp = v[firstIndex];
    v[firstIndex] = v[secondIndex];
    v[secondIndex] = temp;
 
    return v;
}
 
void dij()
{
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({ startV,0 });
    dist[startV] = 0;
 
    while (!pq.empty())
    {
        vector<int> curV = pq.top().v;
        int curCost = pq.top().cost;
        pq.pop();
 
        if (curCost > dist[curV])
        {
            continue;
        }
 
        for (int i = 0; i < m; ++i)
        {
            int firstIndex = commands[i].firstIndex -1;
            int secondIndex = commands[i].secondIndex -1;
            int nextCost = commands[i].cost;
 
            vector<int> swappedV = Swap(curV, firstIndex, secondIndex);
 
            if (swappedV != startV && dist[swappedV] == 0)
            {
                dist[swappedV] = maxNum;
            }
 
            if (curCost + nextCost < dist[swappedV])
            {
                dist[swappedV] = curCost + nextCost;
                pq.push({ swappedV, dist[swappedV] });
            }
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        int num;
        cin >> num;
        startV.push_back(num);
    }
 
    target = startV;
    sort(target.begin(), target.end());
    dist[target] = maxNum;
 
    cin >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> commands[i].firstIndex >> commands[i].secondIndex >> commands[i].cost;
    }
 
    dij();
 
    if (dist[target] == maxNum)
    {
        cout << -1;
    }
    else
    {
        cout << dist[target];
    }
}
 
 

 

 

문제 재해석을 잘해야하는 문제. 그래서 골드1인가보다.

배열의 상태자체를 노드로 생각해야 한다. 그리고 주어진 명령어들(1,3번째 인덱스를 바꾸는데 10의 비용) 은 간선이 되고, 이 명령어로 인해 바뀌는 결과(배열요소변경)은 또 다른 노드가 된다.

 

느낌이 오는가? 최종타겟은 오름차순된 배열이니, 이 배열(노드)까지 가기 위한 최단거리를 구하면 된다.

그렇게하기위해 map<vector<int>, int> 를 dist로 사용한다. 이 문제에서의 노드는 배열이기 때문에, dist의 키값을 배열(백터든 배열이든)으로 둔다.

 

원래 통상적인 y,x로 표현되는 다익스트라문제에선 dist를 [y][x]로 두면 되기때문에 memset을 이용해 최대값들로 초기화시키는데, 여기선 map을 사용한다.

그렇기 때문에 위 코드의 80번째 라인처럼 아직 접근한적 없는 노드일경우 dist에 큰값을 넣어준다음 비교를 수행해줬다.

이부분은 알아서들 처리하면 됨..