백준 10971번: 외판원 순회 2 (C++)

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

10971번: 외판원 순회 2

---

Solved By: DFS

 

해당 문제에 따라 DFS를 짜는 것에 있어서 어려웠던 부분이 있었습니다. DFS를 짤 때, 총 Recursive가 n + 1번이 되고, DFS의 now가 첫 시작 노드라면 마지막에 첫 시작 node로 돌아올 때는 DFS를 어떻게 다시 Recursive Call을 할지 문제였습니다.

 

구글링을 해보면 사실 마지막 Node를 향해 Recursive Call을 할 필요가 없다는 것을 알 수 있습니다.

방문한 Node가 n개가 되면 마지막으로 도착한 node에서 시작 node를 향해 길이 있을 경우, 해당 경로값을 더하여 최솟값을 새로 할당해주면 되기 때문입니다.

 

+비트마스크를 공부하기 위해 풀어보았습니다.

#include <iostream>
#define MAX 11
#define INF 1e9
using namespace std;

int W[MAX][MAX];
bool visited[MAX];
int res = 1e9;
int n;

void dfs(int now, int cnt, int value, int start){
    if(cnt == n){
        if(!W[now][start]) return;
        res = min(res, value + W[now][start]);
        return;
    }
    for(int i = 1; i <= 10; i++){
        if(now == i || W[now][i] == 0 || visited[i]) continue;
        
        visited[i] = true;
        dfs(i, cnt + 1, value + W[now][i], start);
        visited[i] = false;
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> W[i][j];
        }
    }
    
    for(int i = 1; i <= n; i++){
        visited[i] = true;
        dfs(i, 1, 0, i);
        visited[i] = false;
    }
    
    cout << res;
    
    return 0;
}