외판원 순회 2 (feat. 백준, 10971번)

외판원 순회 2
https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int N, start, ans, arr[10][10];
bool visit[10];
void dfs(register int n, register int m, register int cnt){
    if(cnt == N - 1){
        if(arr[n][start])
            ans = min(ans, m + arr[n][start]);
        return;
    }
    for(register int i = 0; i < N; ++i)
        if(arr[n][i] && !visit[i]){
            visit[i] = true;
            dfs(i, m + arr[n][i], cnt + 1);
            visit[i] = false;
        }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N;
    for(register int i = 0, j; i < N; ++i)
        for(j = 0; j < N; ++j)
            cin >> arr[i][j];
    ans = 99999999;
    for(register int i = 0; i < N; ++i){
        start = i;
        visit[i] = true;
        dfs(i, 0, 0);
        visit[i] = false;
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

시작점으로부터 갈수 없는 곳을 제외하고 다시 시작점으로 돌아올때까지의 총 비용을 구하는 문제입니다.

외판원 순회 알고리즘은 기본적으로 dfs 방식으로 푼다는게 정석입니다.

[0][1] -> [1][2] -> [2][0] 과 같이 0에서 다시 0으로 돌아오는 경우의 총 비용의 합입니다.