10971번 - 외판원 순회 2

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

10971번: 외판원 순회 2

#include <iostream>
using namespace std;
int N;
int W[11][11];
bool check[11] = {false};
int ans = 987654321;

//출발 도시, 들린 도시의 개수, 현재 도시, 비용의 합
void dfs(int start, int cnt, int node, int sum)
{
    //모든 도시 들림 && 출발점 도착
    if(cnt == N && start == node)
    {
        if(sum < ans)
            ans = sum;
        return ;
    }
    for(int i=0; i<N; i++)
    {
        //연결되지 않은 경우
        if(W[node][i] == 0)
            continue;
        //방문하지 않음 && 길이 있음
        if(false == check[node] && W[node][i] > 0)
        {
            check[node] = true;
            sum += W[node][i];

            //이미 ans를 넘겼을 경우 탐색 X 
            if(sum <= ans)
                dfs(start, cnt+1, i, sum);

            check[node] = false;
            sum -= W[node][i];

        }
    }
}
int main()
{
    //TSP
    cin >> N;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> W[i][j];
        }
    }

    //각 정점 모두 출발점으로 선택해봄
    for(int i=0; i<N; i++)
    {
        dfs(i, 0, i, 0);
    }
    cout << ans << '\n';
    return 0;
}