10971 - 외판원 순회 2

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

어떤 지점 s에서 출발해서 모든 정점을 거치고 다시 s로 돌아오는 경우를 모두 탐색했다. $O(N!)$
매 번 "모든 정점을 방문했는가?" 를 확인하면서 모두 방문했다면 현재가 s인가(출발점 == 종료점)를 판별해서 그렇다면 그때의 값이 최소가 되게 했다.

이동할 때마다 가중치를 더한다. 모든 정점을 방문했을 때 자신으로 돌아온게 아니라면 답이 아니도록 했다.

어떤 지점 s는 어디건 상관없다. 출발점과 도착점이 같은 지점을 찾는다면, 그 지점이 어디건 정답인 경우의 경로는 똑같이 나온다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

bool visit[11];
int g[11][11], n;

int tsp(int first, int cur){
    bool allSearch = true;
    for(int i=0; i<n; ++i) allSearch &= visit[i];
    if(allSearch && cur == first) return 0;
        
    int r = INF;
    for(int i=0; i<n; ++i){
        if(i != cur && !visit[i]){
            visit[i] = true;
            r = min(r, g[cur][i] + tsp(first, i));
            visit[i] = false;
        }
    }
    return r;
}

int main(){
    int i, j;
    scanf("%d", &n);
    for(i=0; i<n; ++i)
        for(j=0; j<n; ++j)
            scanf("%d ", &g[i][j]);
    
    printf("%d", tsp(1, 1));
    return 0;
}