# 백준 : 외판원 순회 2(10971)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_10971_Traveling%20Salesman%20problem(TSP))

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <cmath>
using namespace std;

long long int map[10][10];
vector <int> nodes;

int main(void)
{
    int count, tempcount;;
    int total = 1;
    long long int weight;
    long long int cal;
    bool noway = false;
    cin>>count;
    for(int i=0; i<count; i++) {
        for(int j=0; j<count; j++) {
            cin>>map[i][j];
        }
        nodes.push_back(i);
    }
    tempcount = count;
    while(tempcount > 0) {
        total *= tempcount;
        tempcount--;
    }
    
    weight = 1000000 * count;
    for(int i=0; i<total; i++) {
        cal = 0;
        noway = false;
        for(int j=0; j<count; j++) {
            if(j == count-1) {
                if(map[nodes[j]][nodes[0]])     cal += map[nodes[j]][nodes[0]];
                else                            noway = true;
            }
            else
            {
                if(map[nodes[j]][nodes[j+1]])   cal += map[nodes[j]][nodes[j+1]];
                else                            noway = true;
            }
        }
        if(noway == false)  weight = min(weight, cal);
        if(next_permutation(nodes.begin(), nodes.end())) {}
    }
    cout<<weight<<endl;
    return 0;
}

풀이

굉장히 빠르고 직관적이게 풀었다. 38%에 가까운 정답률에 비해 실제 푼 시간은 대략 30분내외?
순열 문제를 먼저 풀어보던 찰나에 이런 문제를 만나서 그런지, 순열로 접근해서 쉽게 계산했다.
N개로 이루어진 각 노드를 0부터 N-1까지라고 생각할 때

1. 0, 1, 2, 3 .... N-1개의 순서대로 이루어진 순열을 시작으로
2. next_permutation을 이용한 순열 오름차순 정렬을 이용해서
3. 행렬[i][i+1]의 위치에 있는 녀석이 0이 아닌 경우 weight를 계산
4. 이 중 최소값을 골라주면 된다

한번은 틀렸는데, map[i][i+1]이 0인 경우 해당 weight가 0이 되는데 이러면 최소값이 줄어들게 된다.
결국 행렬[i][i+1]이 0이면 weight 최소값을 계산하지 않도록 flag를 걸어주면 된다.