1314 - 동굴 탐험

step 1

$N+1$개의 비트로 이루어진 2진수를 생각합니다. $i$번째 비트가 0이면 i번째 사람이 왼쪽에 있다는 뜻이고 1이면 오른쪽에 있다는 뜻입니다. $N+1$번째 비트는 지도의 위치입니다. 0이면 지도가 왼쪽, 1이면 오른쪽에 있다는 뜻입니다.

step 2

$N$개의 비트로 이루어진 또 다른 2진수를 생각합니다. 자신에 해당하는 비트가 1인 사람들이 함께 움직입니다. $1010_{(2)}$면 2, 4번 사람이 함께 움직입니다.

믿을 수 있는 사람이 없다거나 무게가 넘어서 건널 수 없는 경우가 있습니다. 1부터 $2^N-1$까지 모든 경우에 대해 이동이 되는지 안되는지 구해 둡니다.

step 3

처음 생각한 $N+1$개의 비트로 이루어진 2진수를 정점으로 생각합니다. 이동이 가능한지, 그때 시간이 얼마나 걸리는지를 간선으로 생각합니다. 그럼 다익스트라를 이용해 이 문제를 해결할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int w[100], t[100];
int r[100];
int dp[20000],n,base=1, l,isValid[20000];
priority_queue<pair<int, int>> q;
void find(int v, int p,int c, int _w, int np, int _t) {
    if (c == n) {
        if (isValid[np] == -1) return;
        int tar = p;
        if ((p & base) == 0) tar = tar + base + np;
        else tar = tar - base - np;
        if (dp[tar] <= dp[p] + _t) return;
        int i;
        dp[tar] = dp[p] + _t;
        q.push({ -dp[tar],tar });
        return;
    }
    if (((p & base) != 0) == (((1 << c) & p) != 0)) {
        if (_w + w[c] <= l) {
            find(v, p, c + 1, _w + w[c], np | (1 << c), _t < t[c] ? t[c] : _t);
        }
    }
    find(v, p, c+1, _w, np, _t);
}
int main() {
    int i, j, k;
    scanf("%d", &n);
    for (i = 0;i < n;i++) {
        scanf("%d%d", &w[i], &t[i]);
    }
    base = (1 << n);
    for (i = 0;i < n;i++) {
        int rel=0, b=1;
        for (j = 0;j < n;j++) {
            char c;
            scanf(" %c", &c);
            if (i == j) c = 'N';
            if (c == 'Y') rel += b;
            b <<= 1;
        }
        r[i] = rel;
    }
    for (i = 1;i < (1 << n);i++) {
        for (j = 0;j < n;j++) {
            if ((i & (1 << j)) != 0) {
                if ((r[j] & i) == 0) break;
            }
        }
        if (j != n) isValid[i] = -1;
        else isValid[i] = 1;
    }
    for (i = 0;i < n;i++) {
        isValid[(1 << i)] = 1;
    }
    isValid[0] = -1;
    for (i = 0;i <= 19000;i++) dp[i] = 2100000000;
    scanf("%d", &l);
    q.push({ 0,0 });
    dp[0] = 0;
    while (q.size()) {
        int v = -q.top().first, p = q.top().second;
        if (p == (1 << (n + 1)) - 1) break;
        q.pop();
        if (v != dp[p]) continue;
        find(v, p, 0, 0, 0, 0);
    }
    printf("%d", dp[(1 << (n + 1)) - 1] == 2100000000 ? -1 : dp[(1 << (n + 1)) - 1]);
    return 0;
}