백준 10971번 외판원 순회 2

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

Algospot TSP1(http://jaimemin.tistory.com/304)과 유형이 같은 브루트 포스(Brute Force) 문제였습니다.

알고리즘은 아래와 같습니다.

1. 외파원은 0번째 도시에서부터 시작한다고 가정하고 나머지 도시들의 모든 순서를 next_permutation을 이용하여 조합해봅니다.

2. 모든 도시를 방문했다면 방문하는데 걸었던 거리를 현재 result와 비교해서 업데이트해줍니다.

-> 다시 0번째 도시까지 돌아오는 거리도 더해줘야합니다!!

3. result를 출력해줍니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <climits>

using namespace std;

 

const int MAX = 10;

 

int city[MAX][MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

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

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

                         cin >> city[i][j];

 

        vector<int> v(N - 1);

        //0부터 시작

        for (int i = 1; i < N; i++)

                 v[i - 1] = i;

 

        int result = INT_MAX;

        do

        {

                 bool flag = true;

                 int sum = 0;

                 for (int i = 0; i < N - 2; i++)

                         //갈 수 없다면 실패

                         if (!city[v[i]][v[i + 1]])

                         {

                                 flag = false;

                                 break;

                         }

                         else

                                 sum += city[v[i]][v[i + 1]];

 

                 if (flag)

                 {

                         if (city[0][v[0]] && city[v[N - 2]][0])

                         {

                                 sum += city[0][v[0]] + city[v[N - 2]][0];

                                 result = min(result, sum);

                         }

                 }

        } while (next_permutation(v.begin(), v.end()));

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~