[백준][C++] 2098번: 외판원 순회 <226>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

2098번: 외판원 순회

생각의 흐름

DP[k][visited] : k: 현재 도시, visited: 방문했던 도시들을 비트로 표현

 

이때 핵심은 방문했던 도시들을 bit 로 저장하는 것 이다.

예를 들어 00001 이라면 0번 도시를 방문, 00011 이라면 0번, 1번 도시를 방문한 것 이다.

 

또한 메모이제이션을 하는 DP배열을 통해 중복해서 값을 구하는 과정을 제거하였습니다.

따라서 맨 처음에 DP 배열을 -1로 초기화 하고, 이후 값을 삽입해주니다.

 

탐색의 시작은 dfs(0, 1)으로 시작하는데, 0번 지점부터 시작하며, 이를 표현하는 bits는 00000001이기 때문에 1을 인자로 전달한다.

 

또한 모든 지점마다 bfs 탐색을 진행하지 않아도 됩니다!

예를 들어 최단 거리가 0 -> 1 -> 2 -> 3 -> 0 이라고 한다면, 1 -> 2 -> 3 -> 0 -> 1 또한 같은 최단거리 입니다.

어디서 시작하든 순회비용이 동일하기 때문 입니다.

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 16
#define INF 1000000000

int MAP[MAX][MAX];
int DP[MAX][1 << 16];

int N;
int fullBit;

int dfs(int curNode, int curBit) {
    if(curBit == fullBit) {
        if(MAP[curNode][0] != 0) {
            return MAP[curNode][0];
        }
        return INF;
    }
    int& ret = DP[curNode][curBit];
    if(ret != -1) {
        return ret;
    }

    ret = INF;
    for(int i = 0; i < N; i ++) {
        int cost = MAP[curNode][i];
        if(curBit & (1 << i) || cost == 0) continue;

        ret = min(ret, dfs(i, curBit | (1 << i)) + cost);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> MAP[i][j];
        }
    }
    fullBit = (1 << N) - 1;

    memset(DP, -1, sizeof(DP));
    cout << dfs(0, 1);

    return 0;
}