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

.

 

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

 

외판원 순회 문제!

 

문제에 대한 설명을 한다면

 

각 마을에서 마을로 이동하는 경로에 대한 비용이 주어지고

 

모든 마을을 돌면서 나오는 최종 비용이 최소가 되는 비용을 찾으라! 이것이다.

 

단 비용이 0인 경우 못가는 곳이다

 

예를들어

3
0 5 0
0 0 3
7 9 0

인 경우, 0번째마을에서 0번쨰 마을로는 못가고(자기자신)

0번째마을에서 2번째마을로 이동을 못한다.

 

그렇다면 여기서 최소는?

 

5+3+7 = 15입니다.

 

해당 예제를 통해 문제를 더 쉽게 설명해 주겠다

 

이 배열을 arr[][] 이라고 하면

arr[0][1]은 0번째마을에서 1번째 마을로 가는 비용 : 10 ,

인 것이다

 

그렇다면?

 

해당 출력으로 나온 최솟값은

 

0>1>3>2>0

의 경로로

 

0>1 : 10

1>3 : 10

3>2 : 9

2>0 : 6

 

으로 35가  나온다

 

 

근데 도시의 수는 10개 이하로 되어있다?

충분히 시간내에 백트래킹 쓰면 되겠다 라는 생각이 든다.

 

그렇다면 저번에 풀었던 n,m 문제와 유사하게 풀면 되겠다!

 

https://lee-soo.tistory.com/17

[DFS] 백준 15649번 N과 M (1,2,3) (C++)

 

가능한 모든 경우의수를 보자는 것이다.

 

즉 모든 순열을 보면 되는것

 

 

그렇다면 이제 순서는

 

1. 모든 순열의 경우의 수를 구함

2.각 순열을 구할 때 마다, 마을에 대한 비용을 계산하여 최솟값 결정

3. 만약 마을의 비용이 0이라면 백트래킹! (return)

 

 

#include <iostream>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

long min1 = 100000001;

bool visited[10];

long arr[10][10];

vector<int> v;

void task(int n, int depth);

int main()

{

    int n;

    cin >> n;

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            cin >> arr[i][j];

        }

    }

    task(n, 0);

    cout << min1 << "\n";

}

void task(int n, int depth)

{

    if (depth == n)

    {

        long sum = 0;

        for (int i = 0; i < n - 1; i++)

        {

            if (arr[v[i]][v[i + 1]] == 0)

                return;

            sum += (arr[v[i]][v[i + 1]]);

        }

        if (arr[v[n - 1]][v[0]] == 0)

            return;

        sum += arr[v[n - 1]][v[0]];

        min1 = min(min1, sum);

        return;

    }

    for (int i = 0; i < n; i++)

    {

        if (!visited[i])

        {

            visited[i] = true;

            v.push_back(i);

            task(n, depth + 1);

            v.pop_back();

            visited[i] = false;

        }

    }

}

해당 코드이다.

 

DFS를 사용하는 함수를 통해

for (int i = 0; i < n - 1; i++)

        {

            if (arr[v[i]][v[i + 1]] == 0)

                return;

            sum += (arr[v[i]][v[i + 1]]);

        }

        if (arr[v[n - 1]][v[0]] == 0)

            return;

 0인 경우 return을 해주는 것을 볼 수 있다!