[C++] 백준 문제풀이 (Back Tracking) 10971번 외판원 순회2

 

 

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

10971번: 외판원 순회 2

 

#include <bits/stdc++.h>

int n;
int ans = INT_MAX;
int w[10][10];
bool visit[10];
bool flag = false;

// 모든 지점을 다 들렸는지 여부를 판단
bool check(){
    for (int i = 0; i < n; ++i){
        if (!visit[i]) return false;
    }
    return true;
}

// 이전 지점, 지금 방문하는 지점, 현재까지의 비용
void travel(int prev, int curr, int val){
    for (int next = 0; next < n; ++next){
        // 연결 되어있지 않음
        if (w[curr][next] == 0) continue;
        if (next == 0){
            // 모든 지점을 다 들린 후 0 에 왔으므로 최소값을 갱신한다.
            if (check()){
                val += w[curr][next];
                ans = std::min(ans, val);
                return;
            }
        }
        else {
            // 다음지점이 이전지점 이라면 다시 되돌아 가는 경우이므로 잘못된 움직임이다.
            if (next == prev) continue;
            // 다음지점이 이미 방문한 지점이라면 가면 안된다.
            if (visit[next]) continue;
            visit[next] = true;
            travel(curr, next, val + w[curr][next]);
            visit[next] = false;
        }
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;

    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
             std::cin >> w[i][j];
        }
    }
    visit[0] = true;
    travel(-1, 0, 0);
    std::cout << ans << "\n";
    return 0;
}