[BAEKJOON] 10971 외판원 순회

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; scanf("%d", &n); vector<vector<int>> map(n, vector<int>(n)); for (int x = 0; x < n; x++) for (int y = 0; y < n; y++) scanf("%d", &map[x][y]); vector<int>DP(n); for (int x = 0; x < n; x++) DP[x] = x; int answer = 2e9; do { bool ok = true; int sum = 0; for (int x = 0; x < n - 1; x++) { if (map[DP[x]][DP[x + 1]]) sum += map[DP[x]][DP[x + 1]]; else ok = false; } if (ok&&map[DP[n - 1]][DP[0]]) { sum += map[DP[n - 1]][DP[0]]; answer = min(answer, sum); } } while (next_permutation(DP.begin(), DP.end())); printf("%d", answer); return 0; }

next_permutation이란

가진 숫자로 만들 수 있는 모든 경우의 수를 출력해주는 함수이다

#include <algorithm>에 내장되어있으며

vector에 들어있는 값을 모든 경우의 수로 나타내어 준다.

백준님의 문제풀이 유투브를 보면서 공부했다.

출처 : https://www.youtube.com/watch?v=im2z6pnn4i4&t=3688s