Difference between r1.1 and the current
@@ -4,18 +4,106 @@
* [https://www.acmicpc.net/problem/10971|외판원 순회 2]
= 참가자 =
= 코드 =
== 15이원준 ==
== 곽정흠 ==
= 아이디어 =
== 15이원준 ==
== 곽정흠 ==
= 참가자 =
*
* 박인서
= 코드 =
== 15이원준 ==
{{{
#include<iostream>
#include<algorithm>
using namespace std;
int arr[12][12] = { 0, };
int dp[12][1 << 12] = { 0, };
int N;
int TSP(int start, unsigned int mid, int dep) {
if (dp[start][mid]) {
return dp[start][mid];
}
if (dep == 1) {
dp[start][mid] = arr[start][0];
return arr[start][0];
}
int ret;
dp[start][mid] = 11000000;
for (int i = 0; i<N; i++) {
if ((1 << i) & mid) {
int tmp = TSP(i, mid - (1 << i), dep - 1);
if (tmp != 0 &&arr[start][i]) {
dp[start][mid] = min(dp[start][mid], arr[start][i] + tmp);
}
//printf("%d %d %d %u %d %d\n",dep, start, i, mid, arr[start][i] +tmp, dp[start][mid]);
}
}
if (dp[start][mid] == 11000000) {
dp[start][mid] = 0;
return 0;
}
return dp[start][mid];
}
int main() {
cin >> N;
unsigned int mid = 0;
for (int i = 0; i<N; i++) {
mid = (mid << 1) + 1;
for (int j = 0; j<N; j++) {
cin >> arr[i][j];
}
}
cout << TSP(0, mid - 1, N) << endl;
}
}}}
== 박인서 =={{{
#include <iostream>
int w[11][11];
bool visit[11] = { false, };
int min = 100000000;
void back(int s, int v, int n, int c,int cnt) {
if (cnt == n && min > c + w[v][s] && w[v][s] != 0) {
min = c + w[v][s];
return;
}
visit[v] = true;
for (int i = 0; i < n; i++) {
if (!visit[i] && min > c + w[v][i] && w[v][i] != 0)
back(s, i, n, c + w[v][i], cnt + 1);
}
visit[v] = false;
}
int main() {
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
std::cin >> w[i][j];
}
back(0, 0, n, 0, 1);
std::cout << min;
return 0;
}
}}}
== 곽정흠 ==
= 아이디어 =
== 15이원준 ==
* '다이나믹은 어려워'로 풀었습니다.
* dfs로 탐색하고 중복되는 과정은 dp에 저장하여 풀었습니다.
== 박인서 == * 백트래킹을 이용(시작점을 무조건 0번이라고 봐도 되는 이유는 순회이므로..)
* back(int s, int v, int n, int c,int cnt)
* s : 백트래킹 시작점
* v : 현재 위치
* n : 도시 갯수
* c : 현재까지의 비용
* cnt : 현재까지 방문한 도시 갯수
* cnt가 n일 때 c의 값을 비교하여 최솟값을 구하면 됩니다.
== 곽정흠 ==
3.1. 15이원준 ¶
#include<iostream>
#include<algorithm>
using namespace std;
int arr[12][12] = { 0, };
int dp[12][1 << 12] = { 0, };
int N;
int TSP(int start, unsigned int mid, int dep) {
if (dp[start][mid]) {
return dp[start][mid];
}
if (dep == 1) {
dp[start][mid] = arr[start][0];
return arr[start][0];
}
int ret;
dp[start][mid] = 11000000;
for (int i = 0; i<N; i++) {
if ((1 << i) & mid) {
int tmp = TSP(i, mid - (1 << i), dep - 1);
if (tmp != 0 &&arr[start][i]) {
dp[start][mid] = min(dp[start][mid], arr[start][i] + tmp);
}
//printf("%d %d %d %u %d %d\n",dep, start, i, mid, arr[start][i] +tmp, dp[start][mid]);
}
}
if (dp[start][mid] == 11000000) {
dp[start][mid] = 0;
return 0;
}
return dp[start][mid];
}
int main() {
cin >> N;
unsigned int mid = 0;
for (int i = 0; i<N; i++) {
mid = (mid << 1) + 1;
for (int j = 0; j<N; j++) {
cin >> arr[i][j];
}
}
cout << TSP(0, mid - 1, N) << endl;
}
3.2. 박인서 ¶
#include <iostream>
int w[11][11];
bool visit[11] = { false, };
int min = 100000000;
void back(int s, int v, int n, int c,int cnt) {
if (cnt == n && min > c + w[v][s] && w[v][s] != 0) {
min = c + w[v][s];
return;
}
visit[v] = true;
for (int i = 0; i < n; i++) {
if (!visit[i] && min > c + w[v][i] && w[v][i] != 0)
back(s, i, n, c + w[v][i], cnt + 1);
}
visit[v] = false;
}
int main() {
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
std::cin >> w[i][j];
}
back(0, 0, n, 0, 1);
std::cout << min;
return 0;
}
