백준 2098 외판원 순회

백준 문제를 다시 잡아봤다. DP문제에서 진짜 엄청 유명한 문제인 TSP를 풀어보고 싶어서 찾았다. 근데 진짜 TSP 키워드로 구글에서 검색하면 별의 별 곳 응용이 다 나오더라. 가장 많이 보이는게 경로 문제, 최근 드론 배달이 많이 연구 되고 있는데 그쪽 관련된 이미지가 많이 나오는 것 같다.

 

문제는 심플하다. 유향 가중치 그래프를 인접 행렬로 입력 받아서, 모든 노드를 방문하고 제 자리로 돌아오는 경로를 찾는 것 - 이 문제에서는 비용만 구하면 된다.

처음 접근은 DFS를 사용해서 DP에 저장해가면서 풀어보는 방식이었다. 직전 문제인 도둑질에서도 같은 접근 방법을 사용했었다. 근데 코드 구현 중, 탐색 중간에 되돌아가거나 다음 경로가 없을 때 너무 복잡해져서 엎었다...

그래서 이걸 어떻게 하나... 하다가 다른 DFS 접근방법을 찾았다...

 

원래 접근했던 DFS는 스택으로 방문한 노드들을 저장했었다. 이 경우, 구현이 지나치게 복잡해지는 것 같았다. DP로 저장을 해야되는데 이 상태를 어떻게 저장을 해야하나... 했는데 찾은 방법에서는 bit mask로 상태를 표현했다. 각 비트를 노드로 생각하고, 1이 노드 갯수만큼 있으면 전부 방문한 것으로 본다. 노드는 최대 16개이므로, int 변수로 충분히 표현 가능하다.

 

dp배열은 dp[i][j] = i번째 노드에서, j상태일때 방문 경로 비용을 의미한다. DFS 탐색을 할 때, 탈출조건은 모든 비트가 1인지 확인하는 것이다. 그 경우에는 모든 노드를 방문한 상황이므로, 탈출이 발생되게 된다.

---

#include <iostream>
#include <vector>
#include <climits>

// std::vector<std::vector<int>> &g_map;
// std::vector<std::vector<int>> &g_dp;
// std::vector<std::vector<int>> paths;
int g_answer_bit;
int g_n;
// #define INF 987654321
const int INF = 987654321;

int dfs(int cur_node, int cur_bit, std::vector<std::vector<int>> &g_map, std::vector<std::vector<int>> &g_dp) //레퍼런스로 안받으면 계속 복사해서 미칠듯이 탐색...
{
    if (cur_bit == g_answer_bit) // 모든 노드 방문했을때
    {
        if (g_map[cur_node][0] == 0) // 현재 노드에서 0으로 돌아가는 길이 있나?
            return INF; // 없으면 inf
        else
            return g_map[cur_node][0]; // 있으면 해당 값 리턴
    }

    if (g_dp[cur_node][cur_bit] != -1) // dp 배열에 이미 차있으면 
        return g_dp[cur_node][cur_bit]; // 그대로 리턴
    g_dp[cur_node][cur_bit] = INF; // 최소값 찾기위해 inf로 초기화

    for (int i = 0; i < g_n; i++) // cur_node에서 각 노드 순회
    {
        if (g_map[cur_node][i] == 0) // cur_node에서 i 번째 노드 갈 수 없으면 다음노드로
            continue;
        if ((cur_bit & (1 << i)) == (1 << i)) // i 번째 노드를 이미 방문했으면 다음노드로
            continue;
        // 현재 값과, i 노드 간 값의 최소값 구하기 -> 다 돌고 나면 밑까지 다 탐색한 값
        g_dp[cur_node][cur_bit] = std::min(g_dp[cur_node][cur_bit], g_map[cur_node][i] + dfs(i, cur_bit | 1 << i, g_map, g_dp));
    }

    return g_dp[cur_node][cur_bit];
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    int n;
    int answer = -1;
    std::cin >> n;

    std::vector<std::vector<int>> map(n, std::vector<int>(n, 0));
    std::vector<std::vector<int>> dp(n, std::vector<int>(1 << 16, -1));
    // g_map = map;
    // g_dp = &dp;
    g_n = n;
    g_answer_bit = (1 << n) - 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int path;
            std::cin >> path;
            map[i][j] = path;
        }
    }
    
    answer = dfs(0, 1, map, dp);
    std::cout << answer;
}

/*
회고
DFS를 사용해서 dp에 저장해가면서 풀어볼까? 했는데 탐색 중간에 되돌아가거나 다음 경로를 찾을 때, 경로가 없을 경우 너무 복잡해져서 엎었다.
벡터를 global scope에 저장하는 방법을 찾아야겠다.
*/

 

삽질을 여러번 했는데, map과 dp를 함수에 넘겨줄때 레퍼런스로 주지 않아서 무한루프가 발생했었다... 그리고 TSP의 솔루션을 탐색할 때, 한 노드에서 한번만 탐색하면 된다는 생각도 여러번 머리속에서 경로 돌려보고 들었다. 모든 노드를 최소 비용으로 순회하는 경로가 있으면, 그 경로는 어떤 노드에서도 동일하게 나온다...

유명한 문제라서 한번 풀어봐야겠다... 했는데 좀 신기했다. 엄청 오래된 문제고, 요즘에 실제로도 많이 쓰이나 싶었는데 여기저기서 아직도 많이 언급되는것이 특이한 지점인것 같다.

 

오늘도 평온한 하루가 되길. 슨민.