https://www.acmicpc.net/problem/10971
#10971: 세일즈맨 2
도시의 수 N이 첫 번째 줄에 주어집니다.
(2 ≤ N ≤ 10) 비용 행렬은 다음 N 행에 제공됩니다.
각 행렬 요소는 1,000,000 이하의 양의 정수이며 갈 수 없으면 0을 지정합니다.
W(i)(j)는 도시 i에서 j입니다.
www.acmicpc.net
문제
여행하는 세일즈맨 문제는 여행하는 세일즈맨 문제(TSP)라고 하며 컴퓨터 과학에서 가장 중요한 문제 중 하나입니다.
문제에는 다양한 변형이 있지만 여기서는 가장 일반적인 유형의 문제를 살펴보겠습니다.
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까지 가는 비용을 나타냅니다.
항상 반복할 수 있는 경우만 입력으로 제공됩니다.
누르다
첫 번째 줄에 외판원의 여정에 필요한 최소 비용을 인쇄하십시오.
샘플 입력 1
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0예제 출력 1
35import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int()() W;
static boolean() visited;
static int result = (int) 10e9;
// c = 현재 몇 번째 방문 도시인지, s = 어디서부터 왔는지, cost = 비용이 얼마인지
private static void tsp(int c, int s, int cost) {
if(c == N && W(s)(1) !
= 0) { // 마지막 도시에서 출발 도시로 가는 길이 있을 때만
result = result < cost + W(s)(1) ? result : cost + W(s)(1);
return;
}
for (int i = 2; i <= N; i++) {
if(!
visited(i) && W(s)(i) !
= 0) { // 방문한 적 없고 길이 있을 때만
visited(i) = true; // 방문 처리
tsp(c + 1, i, cost + W(s)(i));
visited(i) = false;
}
}
}
public static void main(String() args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// N 입력
N = Integer.parseInt(br.readLine());
// 비용 행렬 입력
W = new int(N + 1)(N + 1);
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
W(i)(j) = Integer.parseInt(st.nextToken());
}
}
// 방문 체크 배열
visited = new boolean(N + 1);
// tsp
tsp(1, 1, 0);
// 출력
System.out.println(result);
}
}