2098

백준 2098번

Link: 2098번: 외판원 순회

---

문제 설명

그 유명한 Traveling Salesperson 문제다.

NP-hard 문제지만, 여기서는 인풋이 좀 작아서 시간안에 풀리도록 만들었다.

푸는 방법은 사실 단순한데, DFS + Memoization으로 풀면 된다.

그런데 여기서 중요한 점이 하나 있는데, 출발점을 제외한 모든 도시들은 단 한번만 방문할 수 있다는 점이다.

이 방문 여부를 표시하기 위해 비트마스킹을 사용한다는 점이 큰 차이점이다.

처음에는 비트마스킹을 안쓰고 단순 DP로만 풀어보려고 했는데, 어떻게 푸는지는 알겠는데 도저히 구현이 안되더라.

겨우겨우 구현해서 제출해보니 역시나 틀린 답이었다.

한참 더 고민하다 답을 찾아봤고, 단순 DP로 풀리는 문제가 아니라는 점을 깨달았다.

푸는 방법은 다음과 같다.

우선 DFS 함수의 인자를 인덱스와 방문 여부로 받도록 한다.

여기에 0과 1을 넘겨, 첫 도시에서 시작한다는 점을 명시하여 DFS 함수를 실행한다.

DFS 함수의 종료 조건은 모든 도시를 방문했다는 경우로, visit이 1을 N만큼 왼쪽으로 shift한 값 - 1과 같은 값이 되면 종료한다.

이때 그냥 종료하면 안되고, 마지막 방문 도시에서 처음 도시로 가는 길이 없다면 불가능한 경우이므로 무한대값을 리턴한다.

길이 있다면 그 길을 택했을때의 cost 값을 리턴한다.

종료조건이 아닐 경우, 현재 인덱스 값과 visit을 통해 DP 배열의 값을 받아온다.

이때 중요한 점은 DP 배열의 값을 받아오는 것이 아닌 주소값을 받아와야 한다는 것. 이렇게 하면 DP 배열을 일일이 갱신하지 않고 주소값을 받아온 변수를 변경하면 알아서 DP배열의 값도 바뀐다.

포인터 연산의 편리함을 다시한번 느끼게 된 계기.

이렇게 받아온 값이 초기값인 -1이 아니라면 이 값을 그대로 리턴해준다.

만약 초기값에서 갱신되지 않았다면, 우선 매우 큰 값으로 설정해 준다.

그 다음, 현재 위치에서 연결되었으며 앞에서 방문하지 않은 도시들에 대해 재귀함수로 탐색하며 최소값을 갱신해 준다. 이때 방문 여부를 1을 도시 번호만큼 왼쪽으로 shift하여 표시한다.

이렇게 재귀함수를 돌며 갱신된 값이 곧 답이다.

재귀함수를 돌며 탐색하는 부분이 가장 이해하기 어려웠는데, 순열을 재귀로 만드는 과정과 같다고 생각하면 이해가 빠르다.

모든 경우를 다 따져가며 최소값을 구하고, 탐색 결과값을 저장하고 이를 불러옴으로써 시간을 단축시킬 수 있는 문제.

앞으로도 문제풀때 중요한 개념들이 여럿 등장했던 중요한 문제다.

비트마스킹, 포인터 연산이 아주 중요한 개념임을 깨닫게 된 문제.

꼭 다시한번 풀어봐야될 문제인 것 같다.

---

정답 코드

//
// Created by Keith_Lee on 04/04/2019.
//

#include <iostream>
#include <string.h>

using namespace std;

int map[16][16] = {0, };
int DP[16][1 << 16] = {0, };

int N;

int cost(int index, int visit){
    if(visit == (1 << N) - 1){
        if(map[index][0] == 0){
            return 987654321;
        }

        return map[index][0];
    }

    int& result = DP[index][visit];

    if(result != -1){
        return result;
    }

    result = 999999999;

    for(int i=0; i<N; i++){
        if(visit & (1 << i) || map[index][i] == 0){
            continue;
        }

        result = min(result, cost(i, (visit | (1 << i))) + map[index][i]);
    }

    return result;
}

int main(){
    cin >> N;

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

    memset(DP, -1, sizeof(DP));

    cout << cost(0, 1) << '\n';

    return 0;
}

---