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, 도시 간 비용을 cost 배열, 도시의 방문처리를 visited배열, 최종 비용을 answer로 선언한다.
> 도시의 수를 입력받고 cost배열, visited배열의 크기를 정의해주고 visited를 false로 초기화한다.
> 각 도시 간 비용을 입력받아 cost에 저장한다.
> 1번 도시부터 시작점으로 잡고 방문처리를 한 뒤 도시를 순회하는 백트래킹 함수 Salesman으로 들어간다.
> 탐색이 끝나면 다른 경우를 위해 방문처리를 되돌린다.
> Salesman은 매개변수로 최초시작점, 직전에 방문한 곳, 지금까지의 비용, 총 방문한 도시의 수를 가진다.
> 매 재귀마다 1부터 N도시까지 보는데 방문처리가 안된 도시만 따진다.
> 그리고 만약 prev 즉, 직전 도시에서 이번에 가기로 뽑은 i도시까지의 비용이 0이면 못가므로 넘어간다.
> 가능한 도시를 뽑으면 방문처리하고 total에 비용을 더해주며 rst도 증가시켜 재귀로 넘긴다.
> 위 과정을 반복하며 rst가 N-1이 되면 모든 도시를 방문한것이므로 다시 시작점으로 돌아가야한다.
> 이때 prev에서 i가는 비용이 0이면 못간다 즉, 시작 도시로 다시 못돌아가므로 끝내준다.
> total에 돌아가는 비용을 더해 최종비용 answer과 최소값 연산으로 최소 비용을 갱신한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//10971번 외판원 순회 2
static int N;
static int[][] cost;
static boolean[] visited;
static int answer = Integer.MAX_VALUE;
static void Salesman(int start,int prev, int total, int rst) {
if(rst == N - 1) {
if(cost[prev][start] == 0) return;
answer = Math.min(answer, total + cost[prev][start]);
return;
}
for(int i = 1; i <= N; i++) {
if(visited[i]) continue;
if(cost[prev][i] == 0) continue;
visited[i] = true;
Salesman(start, i, total + cost[prev][i],rst + 1);
visited[i] = false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
cost = new int[N+1][N+1];
visited = new boolean[N+1];
Arrays.fill(visited, false);
for(int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= N; j++) cost[i][j] = Integer.parseInt(st.nextToken());
}
for(int i = 1; i <= N; i++) {
visited[i] = true;
Salesman(i, i, 0, 0);
visited[i] = false;
}
System.out.print(answer);
}
}
후기
매개변수가 많아져 중간중간 흐름이 조금 헷갈렸지만 할만 했다.
