문제
N개의 도시와 도시 간 이동 비용이 주어질 때, 모든 도시를 정확히 한 번씩 방문하고 출발 도시로 돌아오는 최소 비용을 구하라.
입력
첫째 줄에 N(2~10), 이후 N×N 비용 행렬이 주어진다. 0이면 경로 없음.
출력
최소 순회 비용을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0 | 35 |
풀이
모든 시작점에서 DFS로 순열 탐색하며 최소 비용 순회를 찾는다.
- 각 도시를 시작점으로 설정한다
- DFS로 미방문 도시 중 이동 가능한 도시로 이동하며 비용을 누적한다
- 모든 도시를 방문하면 출발점으로 돌아가는 비용을 더해 최솟값을 갱신한다
- 백트래킹으로 방문 표시를 해제하며 다른 경로를 탐색한다
핵심 아이디어: N이 최대 10이므로 O(N!)의 브루트포스가 시간 내에 가능하다.
코드
package day449;
import java.io.*;
import java.util.*;
public class Day428BOJ10971외판원순회2 {
static long ans = Integer.MAX_VALUE;
static int N;
static int[][] map;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < N; i++) {
visited = new boolean[N];
visited[i] = true;
dfs(i, i, 0);
}
System.out.println(ans);
br.close();
}
public static void dfs(int start, int now, long cost) {
if (check()) {
if (map[now][start] != 0)
ans = Math.min(ans, cost + map[now][0]);
return;
}
for (int i = 1; i < N; i++) {
if (!visited[i] && map[now][i] != 0) {
visited[i] = true;
dfs(start, i, cost + map[now][i]);
visited[i] = false;
}
}
}
public static boolean check() {
for (int i = 0; i < N; i++)
if (!visited[i])
return false;
return true;
}
}복잡도
- 시간: O(N * N!)
- 공간: O(N²)