백준 2098: 외판원 순회 (C++)

문제 링크: www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

풀이 방법

int W[16][16]; //도시 i에서 j로 가기 위한 비용(갈 수 없는 경우는 0)
int dp[16][1 << 16]; //dp[i][j]: 현재 정점 i, 지나온 경로 j일 때 지금까지 든 최소 비용
int complete; // 모든 도시를 다 방문한 상태(2^N-1)

 

어려웠던 부분/새로 알게 된 내용

DFS방식으로 처음에 풀었는데 백준에서 시간 초과가 떴다.

어떤 부분을 메모이제이션 할 지 감이 안 와서 검색했더니 비트마스킹 방식으로 지금까지의 경로를 표현하는 방법으로 dp배열을 구성했다.

비트마스킹 방식 참고 : mygumi.tistory.com/361

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 16000000
using namespace std;

int N; //도시의 수
int W[16][16]; //도시 i에서 j로 가기 위한 비용(갈 수 없는 경우는 0)
int dp[16][1 << 16]; //dp[i][j]: 현재 정점 i, 지나온 경로 j일 때 지금까지 든 최소 비용
int complete;

int dfs(int current, int path) {
    if (path == complete) {
        if (W[current][0] == 0) {
            return INF;
        }
        else {
            return W[current][0];
        }
    }

    if (dp[current][path] != -1) {
        return dp[current][path];
    }

    dp[current][path] = INF;

    for (int i = 0; i < N; ++i) {
        if (W[current][i] == 0) {
            continue;
        }
        if ((path & (1 << i)) == (1 << i)) {
            continue;
        }
        dp[current][path] = min(dp[current][path], W[current][i] + dfs(i, path | 1 << i));
    }
    return dp[current][path];
}

int main(void) {
    scanf("%d", &N);
    complete = (1 << N) - 1;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf("%d", &W[i][j]);
        }
    }

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

    printf("%d", dfs(0, 1));

    return 0;
}