[알고리즘 문제] 백준10971 -외판원 순회2

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

Traveling Salesman problem (TSP)라고 불리는 문제로 CS분야에서 가장 중요하게 생각되는 문제라고 합니다.

 

서울, 부산, 대구, 전주, 광주 5개의 도시가 있을 때 특정 도시에서 출발해 다른 도시를 모두 방문하고 처음 도시로 돌아왔을 때 최소비용을 구하는 문제입니다. 이번 문제에서는 어떤 도시에서 다른 도시로 갈 수 없는 경우가 추가되었습니다. 이런 경우 행렬에서 0으로 표시하였습니다.

 

문제는 dfs와 순열로 풀 수 있습니다.

 

0~ N까지의 도시가 나오고 각각의 출발점을 달리하면서(0,1,2...N) dfs를 하였습니다. 방문한 도시는 다시 방문할 수 없기 때문에 visited[]를 사용하여 체크를 해주었고, 마지막 도시를 방문하고 처음 도시로 돌아와야 하기 때문에 startAt에 처음 도시를 저장하였습니다.

 

#include <iostream>
#include <algorithm>

using namespace std;
int n;
int visited[11];
int arr[11][11];
int startAt;
int result = 987654321;

void travel(int node, int depth, int sum)
{
    if (depth == n - 1 && arr[node][startAt])
    {
        result = min(result, sum + arr[node][startAt]);
        return;
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            if (!visited[i] && arr[node][i])
            {
                visited[i] = true;
                travel(i, depth + 1, sum + arr[node][i]);
                visited[i] = false;
            }
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < n; k++)
        {
            cin >> arr[i][k];
        }
    }

    for (int i = 0; i < n; i++)
    {
        startAt = i;
        visited[i] = true;
        travel(i, 0, 0);
        visited[i] = false;
    }

    cout << result;
    return 0;
}