[백준] 14590 KUBC League (Small) - C++

 

 

 

외판원 순회에서 한 단계 더 발전된 문제이다.

 

dfs를 돌면서 dp 배열을 채운 뒤, 값들을 역추적해서 방문한 순서도 구해줘야 한다.

 

dp[curNode][curState] : 현재 curNode를 탐색하고 있고, curState를 방문한 상태일 때 최대 길이

 

풀이의 편의를 위해 zero base index로 접근하고, 구해야 하는 선수가 1번이라고 했으니 0번으로 설정하고 dfs를 돌리자.

 

 

 

 

#include <cstring>
#include <iostream>

using namespace std;

int N;
int arr[22][22];
int dp[21][1 << 21];

int dfs(int curNode, int curState){
    int &res = dp[curNode][curState];
    if(res != -1) return res;

    res = 0;

    for(int i=0; i<N; i++){
        if(arr[curNode][i] == 0) continue;
        if(curState & (1 << i)) continue;

        res = max(res, dfs(i, curState | 1 << i) + 1);        
    }
    return res;
}

void trace(int curNode, int curState){
    for(int i=0; i<N; i++){        
        if(arr[curNode][i] == 0) continue;
        if(curState & (1 << i)) continue;
        if(dp[curNode][curState] == dp[i][curState | (1 << i)] + 1){
            cout << i+1;
            cout << " ";
            trace(i, curState | (1 << i));
            break;
        }
    }
}

int main(){
    cin >> N;    
    memset(dp, -1, sizeof(dp));

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> arr[i][j];            
        }
    }

    int L = dfs(0, 1);

    cout << L+1;
    cout << "\n";

    cout << 1;
    cout << " ";

    trace(0, 1);

    return 0;
}