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

문제링크 : https://www.acmicpc.net/problem/10971

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

int n, answer = INT_MAX, start;
int arr[11][11];
bool visited[11];

void dfs(int idx, int cost, int depth)
{
    if(depth==n-1) //최대 깊이 도달
    {
        if(arr[idx][start])
        {
            answer = min(answer, cost + arr[idx][start]);
            return;
        }
    }

    for(int i=0; i<n; i++)
    {
        if(visited[i] || !arr[idx][i]) continue;
        visited[i] = 1; //현재 숫자 선택
        dfs(i, cost + arr[idx][i], depth+1);
        visited[i] = 0; //백트래킹 (선택 취소)
    }

}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    for(int i=0; i<n; i++)
    {
        start = i;
        visited[i] = 1;
        dfs(i, 0, 0);
        visited[i] = 0;
    }

    cout << answer;
    return 0;
}

 

백트래킹을 살짝 응용한 문제이다.

백트래킹의 재귀함수에 깊이 뿐만 아니라, 현재 인덱스와 비용도 같이 넘겨주어야 한다.

또한 모든 위치를 기준으로 비용을 측정하기에, start를 따로 저장하여 모든 케이스에 대해 재귀함수를 돌려주어야 한다.