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

백준의 외판원 순회2(10971) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는, 모든 시작점에서 갈 수 있는 모든 나라들을 거쳐 다시 시작점으로 돌아올 수 있는지 모든 경우의수를 다 해 보고

   답을 도출해내는 브루트포스 문제이다.

  

2) 문제에 접근하는 방법은 간단하다. 한번 갔던 나라를 재 방문 하는 것은 비용을 낭비하는 것일 수 있으므로, 이미 한번 방문

   한 나라들은 방문했다는 표시를 해주고, 방문한 나라의 갯수와, 비용을 계속해서 재귀를 통해서 구현하면 된다.

   만약 모든 나라를 방문했다면, 마지막에 방문한 나라에서 처음 시작한 나라로 다시 돌아올 수 있느지 판단 후 돌아올 수

   있다면 비용을 비교하여 최솟값을 갱신해 주면 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 10 + 1
using namespace std;
 
int N, Answer = 987654321;
int MAP[MAX][MAX];
bool Visit[MAX];
int Start_Node;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void DFS(int Node, int Cost, int Cnt)
{
    if (Cnt == N - 1)
    {
        if (MAP[Node][Start_Node])
        {
            Answer = Min(Answer, Cost + MAP[Node][Start_Node]);
            return;
        }
    }
 
    for (int i = 1; i <= N; i++)
    {
        if (MAP[Node][i] && Visit[i] == false)
        {
            Visit[i] = true;
            DFS(i, Cost + MAP[Node][i], Cnt + 1);
            Visit[i] = false;
        }
    }
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        Start_Node = i;
        Visit[i] = true;
        DFS(i, 0, 0);
        Visit[i] = false;
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}