[백준] 2098 - 외판원 순회

www.acmicpc.net/problem/2098

2098번: 외판원 순회

  컴공 전공필수 과목인 알고리즘 수업을 들으면 동적계획법/DP을 배우게되면 대표적으로 배우게 되는 사례가 피보나치 수열과 외판원 순회 TSP(Travelling salesman problem)이다. 그런데 대학 졸업한지가 이미 10년이 넘은 시점에 이 문제를 보니, 전형적인 외판원 순회 문제라면서 문제 설명이 이것도 친절하지가 않다;;;

 외판원 순회 문제에 대한 설명은 내가 하는 것보다 위키가 더 설명이 잘 되어 있다.

ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C

외판원 문제 - 위키백과, 우리 모두의 백과사전

 이 문제를 푸는 방법은 정말 여러가지 방법이 존재한다고 하는데, 알고리즘 시간에 배우는 가장 기본적인 방식은 DFS를 통한 완전탐색이다. 다만 특정 노드의 방문 정보를 저장하여 dp[현재위치][현재까지 방문한 포인트]의 최소값을 갱신해 나가야 한다.

#include <stdio.h>
#include <string.h>
using namespace std;

#define min(A, B) (((A) < (B)) ? (A) : (B))

int N, visitedAll;
int map[16][16];
int cost[16][1 << 16];

int tsp(int cur, int visited)
{
    if (visited == visitedAll)
    {
        if (map[cur][0] == 0)
            return 0x0FFFFFFF;
        else
            return map[cur][0];
    }

    if (cost[cur][visited] != -1)
        return cost[cur][visited];
    cost[cur][visited] = 0x0FFFFFFF;

    for (int i = 0; i < N; i++)
    {
        if (map[cur][i] == 0)
            continue;
        if ((visited & (1 << i)) == (1 << i))
            continue;

        cost[cur][visited] = min(cost[cur][visited], map[cur][i] + tsp(i, visited | 1 << i));
    }
    return cost[cur][visited];
}

int main(void)
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    visitedAll = (1 << N) - 1;

    memset(cost, -1, sizeof(cost));
    printf("%d\n", tsp(0, 1));

    return 0;
}