10971. 외판원 순회2

www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

모든 이동할 도시의 순서를 구해서 그 값을 각각 구한후 그 최소값이 답.

4개의 도시가 있으면

[1,2,3,4] 즉 1에서2, 2에서3, 3에서4, 4에서1 로 이동하니까 그 비용을 구하고

next_permutation으로 모든 이동가능한 경로를 구한다.

[1,2,3,4], [1,2,4,3], [1,3,2,4] ... 

이 모든 경우에서 각각 비용을 구함.

---

 

처음에 이렇게 했다가 제출 했더니 틀렸다고 뜸.

다시 보니까 길이 막혀있는 경우도 있었다.

어떻게 할지 고민했는데 생각해보니 만약 길이 막혀있으면 결국 돌아서 가야된다는건데

그렇게되면 절때 최소값이 될수 없다. 

그러니까 막혀있는 길이 있으면 그냥 예외처리 해주면 된다.

 

---

위에처럼 해서 냈는데 또 틀렸다고 나왔다 ㅋㅋ.

다시 보니까 마지막 도시에서 처음으로 돌아올때도 길이 막혀있으면 예외처리를 해줘야하는데 뺴먹음.

 

---

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int city[11][11]; /// 비용 행렬
    int c[11]; /// 순열
    int res = 0;

    int n; /// 도시의 수
    cin >> n;

    for(int i = 1; i <= n; i++) { /// 비용 행렬 입력, idx맞추기 위해 1부터
        for(int j = 1; j <= n; j++) {
            cin >> city[i][j];
        }
    }

    for(int i = 1; i <= n; i++) { /// permutation 돌릴 초기 순열 1,2,3,4..,n
        c[i] = i;
    }

    int cnt = 0;
    do { /// c 순열 돌리면서 각 도시간 비용 더함
        int sum = 0;
        for(int i = 1; i < n; i++) {
            if(city[c[i]][c[i+1]] == 0) { /// 갈 수 없는 길이 있으면
                sum = res + 100; /// 지금의 res에 값을 더해 절때 최소값이 될수없게함(예외처리)
                break;
            }
            sum += city[c[i]][c[i+1]];
            
        }

        /// 마지막에서 처음도시로 돌아갈때도 갈 수 없으면 예외처리
        if(city[c[n]][c[1]] == 0) sum = res + 100;
        sum += city[c[n]][c[1]]; /// 처음 도시로 다시 돌아가는 비용

        if(cnt == 0) res = sum; /// min값 구하기위해 최초 한번만 res에 결과값 넣음.
        cnt++;

        res = min(res, sum); /// 최소값 갱신.

    } while(next_permutation(c+1, c+n+1));

    cout << res;
}