[BOJ/C++] 백준 28079 - 배 옮기기

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

28079번: 배 옮기기

 

Bridge and torch problem과 유사한 문제로, 배가 한 번 이동하고 나면 다시 돌아와야 다음 과정을 진행할 수 있다는 점이 특징이다. 모든 배를 강 건너편 (오른쪽)으로 이동시키는 가장 최소 시간을 출력하자.

 

1. 문제의 상태를 비트마스크를 이용해 하나의 정점으로 만들어 그래프를 생성한다.

• 배의 크기 순대로 정렬 후, 강을 건너지 않은 배들은 0, 강을 건넌 배들은 1로 표현하였다.
• 그래프 생성 시, 모든 부분집합에 대해 이중 for문으로 두 척의 배를 한 번에 이동시키는 모든 경우를 정점으로 표현하여, 배가 이동하는 시간을 cost로 하여 간선을 연결해주었다.
• 같은 크기의 배가 여러 대 있을 수 있으므로, 위치 상으로는 더 뒤쪽에 있을지 몰라도 값이 같은 배를 싣게 될 수 있다. 따라서 배의 크기가 같은 경우는 패스하도록 continue 구문을 넣는다.

2. 그래프에 다익스트라 알고리즘을 적용한다.

• 출발점은 0, 도착점은 (1 << n) - 1로 설정해서 모든 배가 왼쪽에 있는 상태에서 모든 배가 오른쪽에 있는 상태로 이동하는 방법들 중 최소 비용을 구한다.
• 배가 이동할 수 있는 모든 경우에 대해 배를 이동시키고, 돌아오는 것을 반복하며 각 상태의 최소 거리를 갱신한다.
• 마지막에 dist[end]를 출력하면 답을 구할 수 있다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <tuple>
#include <cmath>
#define MAX 65538
#define INF 987654321
using namespace std;

struct Edge {
    int to;
    int cost;
    Edge(int to, int cost) : to(to), cost(cost) {}
};

vector<Edge> a[MAX];
int dist[MAX];
bool check[MAX];

int findIndex(int y) {
    if (y == 0) return -1;
    int position = 0;
    while ((y & 1) == 0) {
        y >>= 1;
        position++;
    }
    return position;
}

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

    int n; cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++)
        cin >> b[i];
    if (n == 1) {
        cout << b[0] << endl;
        return 0;
    }
    sort(b.begin(), b.end());

    // 모든 배가 크기가 같다면 -1
    bool isOk = false;
    for (int i = 1; i < n; i++)
        if (b[i] != b[i - 1]) isOk = true;
    if (!isOk) {
        cout << -1 << endl;
        return 0;
    }

    // 그래프 생성
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            // 왼쪽 -> 오른쪽 
            if ((i & (1 << j)) == 0) {
                for (int k = 0; k < j; k++) { // 크기가 더 작은 배들 중 왼쪽에 있는 것들
                    if ((i & (1 << k)) != 0 || b[j] == b[k]) continue;
                    int next = ((i | (1 << j)) | (1 << k));
                    a[i].emplace_back(Edge(next, b[j])); // 2척이 가는 경우
                }
            }
        }
    }

    // 다익스트라 알고리즘 
    priority_queue<pair<int, int>> q; // (dist, i)
    int start = 0, end = (1 << n) - 1;
    q.push(make_pair(0, start));
    for (int i = 0; i < MAX; i++)
        dist[i] = INF;
    dist[start] = 0;
    while (!q.empty()) {
        int d, x; tie(d, x) = q.top(); q.pop();
        if (check[x]) continue;
        check[x] = true;
        for (int i = 0; i < a[x].size(); i++) { // 다음으로 갈 수 있는 정점
            int y = a[x][i].to;
            int cost = a[x][i].cost;

            if (y != end) { // 오른쪽에서 왼쪽으로 배를 이동
                int minIndex = findIndex(y & -y);
                int cnt = 0; 
                bool isAllSame = true; 
                for (int j = 0; j < n; j++) {
                    // 왼쪽에 있는 것들 크기가 다 같다면 false
                    if ((y & (1 << j)) == 0 && b[j] != b[minIndex])
                        isAllSame = false;
                }
                if (isAllSame) {
                    // 그 다음 작은 것으로 선택 (겹치는 게 있을 수 있다.)
                    int temp = y; 
                    while (b[findIndex(temp & -temp)] == b[minIndex]) {
                        temp &= (temp - 1); // 최하위 비트 삭제
                    }
                    minIndex = findIndex(temp & -temp);
                }
                cost += b[minIndex];
                // 1인 상태인 minIndex를 0으로 바꾼다. 
                y &= ~(1 << minIndex);
            }

            if (dist[y] > dist[x] + cost) {
                dist[y] = dist[x] + cost;
                q.push(make_pair(-dist[y], y));
            }
        }
    }
    if (dist[end] == INF) cout << -1 << endl;
    else cout << dist[end] << endl;

    return 0;
}

생각해내기 어려웠던 예외는 다음과 같다.

• 배가 1개인 경우 바로 출력한다.
• 처음에 주어진 배들의 크기가 모두 같은 경우, 배를 모두 옮기는 것이 불가능하다.
• 강 건너에 있는 배들 중 무조건 가장 작은 것을 타고 돌아오면 된다고 생각했었다. 그러나 반례 (1, 1, 1, 2) 가 주어졌을 때, (1, 1 / 1, 2)의 상태로 배가 위치할 수 있다. 이 경우에는 왼쪽 배들이 모두 1이기 때문에 오른쪽에서 1을 타고 돌아온다면 문제를 풀수 없다. 따라서, 제일 작은 배를 타고 오되 왼쪽에 있는 배들이 제일 작은 배와 모두 크기가 같다면 그 다음으로 작은 배를 타고 와야 한다. 나는 코드 상에서 isAllSame 변수로 왼쪽 배들이 모두 minIndex와 같은 지 검사하고, 만약 그렇다면 최하위 비트를 찾아 없애며 그 다음 큰 값을 찾아주는 방식으로 예외처리 하였다.