문제 링크

백준 1029 - 그림교환

최초 접근 과정

1. N의 범위가 2~15로 상당히 작은 편이다
2. 한번 그림을 산 사람이 그림을 다시 살 수는 없다.

이 두 조건을 보고 그냥 DFS로 모든 경우의 수를 탐색해 볼까? 라는 생각을 했었다.
그러나 모든 경우의 수를 탐색하려면 정점을 방문하는 횟수만 해도 14!이 되어서 시간 초과가 나게 될 것이다.

정답 접근 과정

여기까지 생각하고 난 뒤, 가능한 풀이 방법은 2가지 정도 떠올랐다.

1. 백트래킹으로 가지치기
2. DP

1. 백트래킹

1번 백트래킹의 경우, 어떤 경우 가지를 쳐 낼 수 있는지 생각해 보았다.
백트래킹을 사용하면 그림을 팔 적절한 사람(자기가 산 가격보다 같거나 더 비싸게 사 줄 사람)이 없는 경우 더 깊게 탐색을 진행하지 않고 리턴함으로써 경우의 수를 줄여볼 수 있겠단 생각이 들었다.

그러나 이런 경우는 그림 매입가가 모두 똑같은 테스트케이스에서 DFS를 통한 브루트포스와 동일하게 작동하므로 이 역시 시간초과를 피할 수 없겠다는 판단이 들었다.

2. DP

2번 DP의 경우, 탐색을 하면서 동일한 노드(사람)에 자주 방문하기 때문에 특정 사람이 앞으로 몇명의 사람에게 더 그림을 팔 수 있는지 저장해 두면 이를 재활용하여 탐색 깊이를 확 줄일수 있겠다는 생각이 들었다.
다만, A라는 같은 사람에게 그림이 전달되더라도 A에게 그림이 도달하기 이전 어떤 사람들의 손을 거쳐왔는지에 따라서 A가 그림을 팔 수 있는 사람의 수가 달라질 수 있다.(그림을 한 번 산 사람은 두 번 살 수 없기 때문)
따라서 DP테이블에는 어떤 사람에게 그림이 도달하기까지 누구의 손을 거쳤는지에 대한 정보도 필요하다고 판단했다.
이 정보를 어떻게 저장할까 생각하다 N의 범위가 2~15로 매우 작았던 것을 떠올려서 비트마스킹을 사용해야겠다는 생각이 들었다.

2^15 x 15 = 1024 x 32 x 15 = 491520

이므로, DP 테이블의 크기 역시 적당하게 나와서 '이거구나!' 했다.

결과적으로 DP테이블을 비트마스크 값과 사람 번호 2개를 인덱스로 갖는 2차원 배열로 선언하고, DFS를 돌면서 DP값이 저장된 노드를 만나면 DP 테이블의 값을 리턴하는 방식으로 시간 복잡도를 줄여서 통과할 수 있었다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int arr[15][15];
int dp[1024 * 32][15];

int DFS(int cur, int price, int bits)
{
    bits = (bits | (1 << cur));

    if (dp[bits][cur]) 
        return dp[bits][cur];

    for (int next = 1; next < N; next++)
    {
        if ((bits & (1 << next)) == 0 && arr[cur][next] >= price) 
            dp[bits][cur] = max(dp[bits][cur], DFS(next, arr[cur][next], bits) + 1);
    }

    return dp[bits][cur];
}

int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string str; cin >> str;
        for (int j = 0; j < str.size(); j++)
            arr[i][j] = str[j] - '0';
    }
    
    cout << (DFS(0, 0, 0) + 1);
    
    return 0;
}