1029번: 그림 교환

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


$O(n*2^n)$

모든 (그림을 소유했던 사람 집합, 마지막에 그림을 소유한 사람, 마지막 가격) 쌍이 노드로 존재하는 그래프를 탐색한다.

#include<cstdio>
int n, a[15][15], ck[1 << 15][15][10], r;
void f(int x, int y, int z, int c) {
    if (c > r) r = c;
    ck[x][y][z] = 1;
    for (int i = 0; i < n; i++) if (a[y][i] >= z&&!(1 << i&x) && !ck[1 << i | x][i][a[y][i]]) f(1 << i | x, i, a[y][i], c + 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%1d", &a[i][j]);
    f(1, 0, 0, 1);
    printf("%d", r);
    return 0;
}