[BOJ] 10971 - 외판원 순회2 (C++)

1. 알고리즘

이 문제는 다음순열(Next permutation)을 이용하여 풀 수있는 문제이다. 

2. 전체 소스

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { vector< vector<int> > arr; int num = 0; int result = 0; int min = 0; int cnt = 0; // minimum값을 처음 값으로 초기화 하기위해 사용된다. cnt가 0이면 처음 계산된 값을 min 값으로 초기화 해준다. int flag = 0; // 순열의 길을 더해가다가 다음 길로 갈 수 없는 길(행렬값이 0일 경우)이 나올 경우 이 flag를 true로 바꿔준다. cin >> num; arr.assign(num, vector<int>(num)); vector<int> roadArr(num+1); // 다시 처음으로 돌아와야 하기 때문에 도시 개수를 +1 해주었다. // 이 배열은 도시순환 순열순서를 저장하기 위한 배열이다. for (int i = 0; i<num; i++) { for (int j = 0; j<num; j++) { cin >> arr[i][j]; } } for (int i = 0; i<num; i++) { roadArr[i] = i; // 도시 개수만큼 배열에 index값을 넣어주었다. } // 도시가 4개면 roadArr={0,1,2,3}이 된다. 이 값들은 행렬의 index로 사용된다. do { result = 0; flag = 0; roadArr[num] = roadArr[0]; // 다시 되돌아올 처음 도시를 roadArr마지막 배열에 넣어주었다. for (int i = 0; i < num; i++) { int temp_x; int temp_y; temp_x = roadArr[i]; temp_y = roadArr[i + 1]; if (arr[temp_x][temp_y] == 0) { flag = 1; // 행렬 값이 0 이라는 것의 의미는 temp_x에서 temp_y도시로 갈 길이 없음을 의미함 break; // 더이상 값을 구할 필요가 없으니 loop를 빠져나온다. } result += arr[temp_x][temp_y]; } if(cnt==0 && flag == 0){ // minimum값을 초기화 시켜준다. min = result; cnt++; }else{ if(flag == 0){ if (min > result) min = result; } } } while (next_permutation(roadArr.begin(), roadArr.end()-1)); // 도시 순열 배열의 마지막은 처음 도시로 셋팅해줄 것이기 때문에 end-1까지만 순열을 구한다. cout << min << endl; }

3. 참고사항

4. 문제

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