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

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

 

 

생각흐름

• 배열의 순서를 확인하면서 최솟값을 가지려면 완전 탐색밖에 없다고 판단
• bfs를 사용했고, queue에 안 넣어주는 조건으로 같은 값을 가진 것이 나왔는데 비용이 더 클 때를 들었다.
• 중간에 while 문을 건너 뛰는 조건으로는 queue에서 뽑은 것의 cost가 전역 변수로 선언된 가장 작은 cost 값을 가진 것 보다 클 때를 들었다.

 

 

#include <iostream>
#include <vector>
#include <map>
#include <queue>

#define endl '\n'

using namespace std;

int N, M;
string A = "";
vector<int> B[10];
map<string, int> m;

int minCost = 987654321;

void bfs(){
    queue<pair<int,pair<string, int>>> q;
    q.push({-1,{A, 0}});
    
    while(!q.empty()){
        int previous = q.front().first;
        string a = q.front().second.first;
        int cost = q.front().second.second;
        q.pop();
        
        if(cost>=minCost){
            continue;
        }
        bool isASC = true;
        for(int i =0; i<N-1; i++){
            if(a[i]>a[i+1]){
                isASC=false;
                break;
            }
        }
        if(isASC){
            minCost=cost;
            continue;
        }

        for(int i = 0; i<M; i++){
            if(i==previous){
                continue;
            }
            string aa = a;
            int tmp = aa[B[i][0]-1];
            aa[B[i][0]-1] = aa[B[i][1]-1];
            aa[B[i][1]-1] = tmp;
            if(m[aa]==0 || m[aa]>cost+B[i][2]){
                q.push({i,{aa, cost+B[i][2]}});
                m[aa]=cost+B[i][2];
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N;
    
    for(int i = 0; i<N; i++){
        int tmp;
        cin>>tmp;
        A+=(char)('0'+tmp);
    }
    
    cin>>M;
    
    for(int i = 0; i<M; i++){
        int a,b,c;
        cin>>a>>b>>c;
        B[i].push_back(a);
        B[i].push_back(b);
        B[i].push_back(c);
    }
    
    bfs();
    
    if(minCost==987654321){
        cout<<-1<<endl;
        return 0;
    }
    cout<<minCost<<endl;
    
    return 0;
}