https://www.acmicpc.net/problem/10971
λ¬Έμ
μΈνμ μν λ¬Έμ λ μμ΄λ‘ Traveling Salesman problem (TSP) λΌκ³ λΆλ¦¬λ λ¬Έμ λ‘ computer science λΆμΌμμ κ°μ₯ μ€μνκ² μ·¨κΈλλ λ¬Έμ μ€ νλμ΄λ€. μ¬λ¬ κ°μ§ λ³μ’ λ¬Έμ κ° μμΌλ, μ¬κΈ°μλ κ°μ₯ μΌλ°μ μΈ ννμ λ¬Έμ λ₯Ό μ΄ν΄λ³΄μ.
1λ²λΆν° Nλ²κΉμ§ λ²νΈκ° λ§€κ²¨μ Έ μλ λμλ€μ΄ μκ³ , λμλ€ μ¬μ΄μλ κΈΈμ΄ μλ€. (κΈΈμ΄ μμ μλ μλ€) μ΄μ ν μΈνμμ΄ μ΄λ ν λμμμ μΆλ°ν΄ Nκ°μ λμλ₯Ό λͺ¨λ κ±°μ³ λ€μ μλμ λμλ‘ λμμ€λ μν μ¬ν κ²½λ‘λ₯Ό κ³ννλ €κ³ νλ€. λ¨, ν λ² κ°λ λμλ‘λ λ€μ κ° μ μλ€. (맨 λ§μ§λ§μ μ¬νμ μΆλ°νλ λμλ‘ λμμ€λ κ²μ μμΈ) μ΄λ° μ¬ν κ²½λ‘λ μ¬λ¬ κ°μ§κ° μμ μ μλλ°, κ°μ₯ μ μ λΉμ©μ λ€μ΄λ μ¬ν κ³νμ μΈμ°κ³ μ νλ€.
κ° λμκ°μ μ΄λνλλ° λλ λΉμ©μ νλ ¬ W[i][j]ννλ‘ μ£Όμ΄μ§λ€. W[i][j]λ λμ iμμ λμ jλ‘ κ°κΈ° μν λΉμ©μ λνλΈλ€. λΉμ©μ λμΉμ μ΄μ§ μλ€. μ¦, W[i][j] λ W[j][i]μ λ€λ₯Ό μ μλ€. λͺ¨λ λμκ°μ λΉμ©μ μμ μ μμ΄λ€. W[i][i]λ νμ 0μ΄λ€. κ²½μ°μ λ°λΌμ λμ iμμ λμ jλ‘ κ° μ μλ κ²½μ°λ μμΌλ©° μ΄λ΄ κ²½μ° W[i][j]=0μ΄λΌκ³ νμ.
Nκ³Ό λΉμ© νλ ¬μ΄ μ£Όμ΄μ‘μ λ, κ°μ₯ μ μ λΉμ©μ λ€μ΄λ μΈνμμ μν μ¬ν κ²½λ‘λ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ λ ₯
첫째 μ€μ λμμ μ Nμ΄ μ£Όμ΄μ§λ€. (2 ≤ N ≤ 10) λ€μ Nκ°μ μ€μλ λΉμ© νλ ¬μ΄ μ£Όμ΄μ§λ€. κ° νλ ¬μ μ±λΆμ 1,000,000 μ΄νμ μμ μ μμ΄λ©°, κ° μ μλ κ²½μ°λ 0μ΄ μ£Όμ΄μ§λ€. W[i][j]λ λμ iμμ jλ‘ κ°κΈ° μν λΉμ©μ λνλΈλ€.
νμ μνν μ μλ κ²½μ°λ§ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
μΆλ ₯
첫째 μ€μ μΈνμμ μνμ νμν μ΅μ λΉμ©μ μΆλ ₯νλ€.
λ°±μ€ μ€λ²2.
Traveling Salesman Problem, μ€μ¬μ TSP
μ΄κ±° μκ³ λ¦¬μ¦ μμ μκ°μ λ°°μ λ κ² κ°μ
TSPλ NP-Hard λ¬Έμ μ μΌμ’ μ΄λ€. κ°λ¨ν λ§νλ©΄ κ·Έλ₯ νκΈ° μ΄λ €μ΄ λ¬Έμ λΌλ λ»μ΄λ€
main ideas
1. μΌλ¨ 무μ§μ± dfs...νλ©΄ λλλ°, λ°±νΈλνΉμ μν΄ dfs λ€μμ μνλ₯Ό κΈ°μ‘΄μΌλ‘ λλ €λλ μ½λκ° μμ΄μΌ ν¨.
κ·Έλ¦¬κ³ λͺ¨λ μμμ μ κ³ λ €ν΄μΌνκΈ° λλ¬Έμ μμ νμ -> μ¬κ· μ§μ ν λλ λ°λ³΅λ¬Έ νμν¨
2. λ°©λ¬Ένλ €λ λ€μ λ§μμ λ°©λ¬Ένμ μ΄ μκ±°λ, κ°λ κ²½λ‘κ° μλ€λ©΄ continue
3. λ§μ§λ§ λ§μμμ μΆλ°μ§λ‘ λμκ° μ μμ΄μΌ νλμ κ²½λ‘λ‘ μΈμ λ¨. (μν κ°λ₯)
4. μ΅μκ°μ μ μΈ μ INT_MAXλ‘ ν΄λκ³ , μννλ©΄μ μ΅μκ°μ μ μ₯νκΈ°
λμ νμ΄
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int n;
int w[10][10] = {0};
int visited[10] = {0};
int answer = INT_MAX;
void travel(int start, int now, int cnt, int sum){
if(cnt == n){
if(w[now][start] == 0) return; // λ§μ§λ§ λ§μμμ μΆλ°μ§λ‘ λͺ» λμκ°λ
if(answer > sum + w[now][start]) answer=sum+w[now][start]; // μ΅μκ° λ체
return;
}
for (int i = 0; i < n; ++i){
if(visited[i]==1 || w[now][i]==0) continue; // λ§μλ°©λ¬Έ or κΈΈμμλ
visited[i] = 1;
travel(start, i, cnt + 1, sum + w[now][i]);
visited[i] = 0; // νμ μ’
λ£ ν λ€λ₯Έκ²½λ‘λ‘ νμμ μν΄ λλλ €λκΈ°
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
cin >> w[i][j];
}
}
for (int i = 0; i < n; ++i){
visited[i] = 1;
travel(i, i, 1, 0);
visited[i] = 0; // λ€μ λ°λ³΅μ μν΄ λλλ €λκΈ°
}
cout << answer;
}
'π μκ³ λ¦¬μ¦ > BOJ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[C++/BOJ] 9251 : LCS (DP) (0) | 2023.03.16 |
---|---|
[C++/BOJ] 9465 : μ€ν°μ»€ (DP) (0) | 2023.03.15 |
[C++/BOJ] 9663 : N-Queen (μμ νμ, Backtracking) (0) | 2023.03.06 |
[C++/BOJ] 1158 : μμΈνΈμ€ λ¬Έμ (Queue) (0) | 2023.03.03 |
[C++/BOJ] 7562 : λμ΄νΈμ μ΄λ (BFS) (0) | 2023.03.02 |