More actions
({CREATE}) |
No edit summary |
||
| Line 5: | Line 5: | ||
= 참가자 = | = 참가자 = | ||
* | * 박인서 | ||
= 코드 = | = 코드 = | ||
| Line 11: | Line 11: | ||
== 박인서 == | == 박인서 == | ||
#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; | |||
} | |||
== 곽정흠 == | == 곽정흠 == | ||
| Line 18: | Line 48: | ||
== 박인서 == | == 박인서 == | ||
* 백트래킹을 이용(시작점을 무조건 0번이라고 봐도 되는 이유는 순회이므로..) | |||
* back(int s, int v, int n, int c,int cnt) | |||
** s : 백트래킹 시작점 | |||
** v : 현재 위치 | |||
** n : 도시 갯수 | |||
** c : 현재까지의 비용 | |||
** cnt : 현재까지 방문한 도시 갯수 | |||
== 곽정흠 == | == 곽정흠 == | ||
Revision as of 03:39, 21 September 2016
오늘의 문제
참가자
- 박인서
코드
15이원준
박인서
#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이원준
박인서
- 백트래킹을 이용(시작점을 무조건 0번이라고 봐도 되는 이유는 순회이므로..)
- back(int s, int v, int n, int c,int cnt)
- s : 백트래킹 시작점
- v : 현재 위치
- n : 도시 갯수
- c : 현재까지의 비용
- cnt : 현재까지 방문한 도시 갯수