[순열] BOJ 10971 외판원 순회 2

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

10971번: 외판원 순회 2

- 문제 파악

정수 N 과 NxN의 2차원 배열이 주어진다. i->j 에서 가는 비용은 2차원의 배열에서 [i][j]의 원소값과 같다. 0부터 N-1 까지 순회하는데 비용의 최소값을 출력하라.

 

- 정답

N-1 에서 0으로 돌아오는 것도 계산해야한다.

 

#include "bits/stdc++.h"

using namespace std;

int arr[11][11];
int nCity[11];
int ans = 0x7ffffff;

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        nCity[i] = i;
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
        }
    }

    bool bwhile = true;

    while (bwhile)
    {
        int tmp = 0;
        for (int i = 0; i < n; i++)
        {
            int nPay;

            if(i != n-1)
                nPay = arr[nCity[i]][nCity[i + 1]];
            else
                nPay = arr[nCity[i]][nCity[0]];

            if (!nPay)
            {
                tmp = 0;
                break;
            }
            tmp += nPay;
        }



        if(tmp)
            ans = min(tmp, ans);

        bwhile = next_permutation(nCity, nCity + n);
    }

    cout << ans;

}