BOJ)14590 KUBC League (Small)

문제: icpc.me/14590

외판원 문제(TSP)와 유사한 문제이다.

외판원 문제는 비트마스크 DP로 해결할 수 있다.

dp[state][pos] <- 현재까지 커버한 상태를 state로 가지고 현재 pos의 위치에 서 있을 때 선수 나열의 최대 길이

점화식은 for(i: 1~n) if(a[pos][i] && !((1<<i)&state)) =>max(dp[state|(1<<i)][i]+1 이 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a[22][22];
int dp[1 << 21][21];
int func(int state, int pos) {
    int &ret = dp[state][pos];
    if (ret != -1)return ret;
    ret = 0;
    for (int i = 1; i <= n; i++) {
        if (a[pos][i] && !((1 << i)&state)) 
            ret = max(ret, func(state | (1 << i), i) + 1);
    }
    return ret;
}
void tracking(int state, int pos) {
    for (int i = 1; i <= n; i++) {
        if (a[pos][i] && !((1 << i)&state)) {
            if (dp[state][pos] == dp[state | (1 << i)][i] + 1) {
                printf("%d ", i);
                tracking(state | (1 << i), i);
                break;
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    }
    int r = func(1 << 1, 1) ;
    printf("%d\n1 ", r + 1);
    int idx = 1;
    tracking(1 << 1, 1);
    return 0;
}