백준 10971 풀이
https://www.acmicpc.net/problem/10971
외판원 순회2
TSP라고도 불리는 아주 유명한 문제다.
최초 생각은 dfs를 통해 그래프를 순회하면서 만약 경로가 끊어져있다면 그 경로는 건너뛰고 다른 경로를 검사하는 방식으로 구현하려고 했다.
그런데 구현실력이 부족했던건지 생각대로 코드가 작성이 안되어 힘들었고 결국 방법을 바꾸기로 했다.
- 경로가 이어졌는지 아닌지는 상관없이 방문할 수 있는 모든 경우의 수를 배열에 저장한다.
- 경우의 수마다 비용을 계산한다.
2-1. 이 때 중간에 경로가 끊어진 곳이 있다면 비용을 계산하지 않고 함수를 빠져나온다.
2-2. 처음 위치로 되돌아 가는 경로가 없다면 마찬가지로 비용을 계산하지 않고 함수를 빠져나온다. - 비용 계산이 끝난 후 기존의 min값과 비교해 최소값을 저장한다.
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이 크다면 여러가지로 문제를 일으킬 가능성이 있다고 생각했다.
그래서 처음 생각한 방법대로 구현해보기로 했다.
- 반복문을 돌며 dfs 함수를 호출한다. 이렇게 하면 0에서 출발해서 0으로 돌아오는 경우 부터 n-1에서 출발해서 n-1까지 돌아오는 경우까지 탐색이 가능하다
2-1. dfs 함수 내에서 반복문을 돌면서 graph의 값이 0이면 continue
2-2. 만약 0이 아니고 방문한 index가 아니면 sum값에 비용을 더해주고 dfs 재귀호출 - cnt값이 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];
}
}
}
Author And Source
이 문제에 관하여(백준 10971 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-10971-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)