https://www.acmicpc.net/problem/10971
TSP라고도 불리는 아주 유명한 문제다.
최초 생각은 dfs를 통해 그래프를 순회하면서 만약 경로가 끊어져있다면 그 경로는 건너뛰고 다른 경로를 검사하는 방식으로 구현하려고 했다.
그런데 구현실력이 부족했던건지 생각대로 코드가 작성이 안되어 힘들었고 결국 방법을 바꾸기로 했다.
import java.io.*;
public class Main {
static boolean visited[];
static int n;
static long graph[][];
static long min = Long.MAX_VALUE;
static int arr[];
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String num = br.readLine();
n = Integer.parseInt(num);
graph = new long[n][n];
visited = new boolean[n];
arr = new int[n];
for (int i = 0; i < n; i++) {
String[] tmp = br.readLine().split(" ");
for (int j = 0; j < tmp.length; j++) {
graph[i][j] = Long.parseLong(tmp[j]);
}
}
dfs(0);
bw.write(min + "\n");
br.close();
bw.close();
}
private static void dfs(int cnt) {
if (cnt == n) {
long sum = 0;
for (int i = 1; i < n; i++) {
if (graph[arr[i - 1]][arr[i]] == 0)
return;
else
sum = sum + graph[arr[i - 1]][arr[i]];
}
if(graph[arr[n - 1]][arr[0]] == 0)
return;
else {
sum = sum + graph[arr[n - 1]][arr[0]];
if (sum < min) {
min = sum;
}
}
return;
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
arr[cnt] = i;
dfs(cnt + 1);
visited[i] = false;
}
}
}
}
하지만 위와 같은 방법은 불필요한 경로까지 일단 저장을 하고 검사를 하기 때문에 n이 작다면 상관없지만 n이 크다면 여러가지로 문제를 일으킬 가능성이 있다고 생각했다.
그래서 처음 생각한 방법대로 구현해보기로 했다.
private static void dfs1(int start, int pos, int cnt, int sum) {
if (cnt == n && start == pos) {
min = Math.min(min, sum);
return;
}
for (int i = 0; i < n; i++) {
if (graph[pos][i] == 0)
continue;
if (!visited[pos] && graph[pos][i] != 0) {
visited[pos] = true;
sum += graph[pos][i];
dfs1(start, i, cnt + 1, sum);
visited[pos] = false;
sum -= graph[pos][i];
}
}
}