[백준 28707] 배열 정렬

 

 핵심적인 부분을 떼놓고 보면 그래프 탐색 문제이다. 배열의 상태는 하나의 노드로 생각할 수 있고, 비내림차순 정렬된 상태를 목적 노드로 생각할 수 있다. 목적 노드는 0개일 수도, 여러 개일 수도 있으며, 각 노드에서는 항상 조작의 개수만큼의 간선을 가지게 된다.

 이 때 목적 노드까지 최소 비용으로 도달하는 경우를 찾는 것이기 때문에, 이는 결국 최단 거리 문제라고 할 수 있다. 따라서 BFS나 다익스트라 알고리즘을 고려해볼 수 있다. 

 

 위 부분은 크게 문제될 게 없으니, 이제 남은 것은 배열의 상태를 노드로 나타내는 것이다. 결국 그래프 탐색을 진행하려면 각각의 노드 방문 여부를 체크할 수 있어야 하기 때문이다. 배열은 최대 길이가 8이고, 이를 각 자릿수의 정수로 인덱싱하면 크기가 76,543,210인 int 배열(비용을 저장할 것이므로)이 필요하고, 이는 메모리 제한이 넉넉해서 메모리 초과를 피할 수 있을 지는 모르겠지만(그래프 탐색도 해야하기 때문에 메모리 초과 가능성이 높다) 너무 큰 공간을 차지하며, 심지어 대부분의 공간이 불필요한 공간이다. 또한 상태 정보를 하나하나 나눗셈과 모듈러 연산을 통해 알아내고, 다시 곱셈으로 새로운 상태를 만들어 내야하는데 이는 CPU 입장에선 굉장히 느린 연산이다.

 

 이 문제 조건에서 방문 상태를 효과적으로 나타낼 수 있는 방법은 여러가지가 있겠으나, 풀고 나서 보니 일반적으로는 해시 맵을 많이 택하는 것 같았다. 나는 문제를 풀 때, 해시 맵보다는 비트 마스킹이 먼저 떠올라서 비트 마스킹을 이용했다. 길이가 8인 배열의 인덱스 순서로 상태를 나타낸다고 치면 3bits(0~7에 해당하는 인덱스) * 8(배열의 길이)만큼 필요하므로 3Bytes 정도의 공간을 사용하게 되고, 이런 상태가 2^8개 존재하니까 768Bytes의 공간을 소모한다. 이 때, 비용을 int 값으로 저장하게 되면, 대략 3MBytes 정도를 방문 여부 저장을 위해 사용하게 됨을 추측할 수 있다.

 

 

 위처럼, 3자리씩 끊어서 배열의 0번째 인덱스에 위치한 값(정확히는 값이 기존 배열 내에 위치한 원래 인덱스)을 나타내려는 아이디어다. 위의 경우 0번째 인덱스에 기존 배열의 0번째 값이 들어있고, 1번째 인덱스엔 1번째 값이...와 같은 의미를 지니게 된다.

 특정 위치 인덱스에 들어있는 세 비트 값을 찾아내는 거야 shift 연산과 &연산을 쓰면 간편하게 할 수 있으나, 기존에 존재하던 상태 비트에 대해 특정 인덱스를 나타내는 세 비트를 원하는 비트들로 바꾸는 과정은 조금 코드가 길어진다(각 자리가 1인 경우와 0인 경우를 나눠서 처리해야 함). 그래서 나는 가독성을 위해서 그 부분은 함수를 따로 빼내었다.

 

 

 기존 상태를 나타내는 origin 비트에 대해, order번째 인덱스를 나타내는 세 비트를, 새로 부여하는 세 비트로 변경하는 함수이다.

 

 

 이제 필요한 부분은 다 구상하거나 구현해뒀으므로, 최단 거리 탐색 알고리즘에 그대로 적용해주면 된다. 나는 처음에 일반 큐와 BFS를 이용했는데 그렇게 해도 시간 초과가 나지는 않았다. 92ms 정도가 나오던데, 우선순위 큐와 다익스트라 알고리즘을 적용하니 68ms로 줄었다.

 다 풀고나서 보니까 다들 해시 맵을 많이 이용한 것 같던데, 그 편이 구현 자체는 훨씬 빨랐을 거 같긴하다.. 

#include <iostream>
#include <queue>
#include <vector>
#define INF 987654321

using namespace std;

class Modification {
public:
    int l, r, cost;

    Modification() {
        l = 0;
        r = 0;
        cost = 0;
    }

    Modification(int l, int r, int cost) {
        this->l = l;
        this->r = r;
        this->cost = cost;
    }
};

bool numToBit[8][3] = {
    { false, false, false },
    { false, false, true },
    { false, true, false },
    { false, true, true },
    { true, false, false },
    { true, false, true },
    { true, true, false },
    { true, true, true }
};

vector<int> isVisited(1<<24, INF);

int modifyBit(int origin, int order, bool leftBit, bool midBit, bool rightBit) {
    int newBit = origin;
    if(leftBit) {
        newBit |= 1 << (order*3 + 2);
    } else {
        newBit &= ~(1 << (order*3 + 2));
    }
    if(midBit) {
        newBit |= 1 << (order*3 + 1);
    } else {
        newBit &= ~(1 << (order*3 + 1));
    }
    if(rightBit) {
        newBit |= 1 << (order*3);
    } else {
        newBit &= ~(1 << (order*3));
    }

    return newBit;        
}

int main() {
    int n, m;
    int numArr[8];
    int l, r, c;
    Modification modificationArr[10];

    cin >> n;

    for(int i=0; i<n; i++) {
        cin >> numArr[i];
    }

    cin >> m;
    for(int i=0; i<m; i++) {
        cin >> l >> r >> c;
        modificationArr[i] = Modification(l-1, r-1, c);
    }

    auto cmp = [](pair<int, int> l, pair<int, int> r) {
        return l.second > r.second;
    };

    priority_queue<pair<int, int>, vector<pair<int, int> >, decltype(cmp)> pq(cmp); // {bit, cost}
    int curBit = 0;
    for(int i=0; i<n; i++) {
        curBit = modifyBit(curBit, i, numToBit[i][0], numToBit[i][1], numToBit[i][2]); 
    }
    pq.push({curBit, 0});

    int minCost = INF;
    while(!pq.empty()) {
        auto cur = pq.top();
        pq.pop();

        if(isVisited[cur.first]<=cur.second) {
            continue;
        }

        isVisited[cur.first] = cur.second;
        bool notDesc = true;
        for(int i=1; i<n; i++) {
            if(numArr[cur.first>>(3*i) & 7] < numArr[cur.first>>(3*(i-1)) & 7]) {
                notDesc = false;
                break;
            }
        }
        if(notDesc) {
            minCost = min(minCost, cur.second);
        } else {
            for(int i=0; i<m; i++) {
                auto md = modificationArr[i];
                bool temp[3] = { cur.first & 1<<(md.l*3+2), cur.first & 1<<(md.l*3+1), cur.first & 1<<(md.l*3) };
                int newBit = modifyBit(cur.first, md.l, cur.first & 1<<(md.r*3+2), cur.first & 1<<(md.r*3+1), cur.first & 1<<(md.r*3));
                newBit = modifyBit(newBit, md.r, temp[0], temp[1], temp[2]);

                if(isVisited[newBit]>cur.second+md.cost) {
                    pq.push({newBit, cur.second + md.cost});
                }
            }
        }

    }
    cout << (minCost==INF?-1:minCost);
}