백준 10971 풀이

https://www.acmicpc.net/problem/10971

외판원 순회2

TSP라고도 불리는 아주 유명한 문제다.

최초 생각은 dfs를 통해 그래프를 순회하면서 만약 경로가 끊어져있다면 그 경로는 건너뛰고 다른 경로를 검사하는 방식으로 구현하려고 했다.

그런데 구현실력이 부족했던건지 생각대로 코드가 작성이 안되어 힘들었고 결국 방법을 바꾸기로 했다.

1. 경로가 이어졌는지 아닌지는 상관없이 방문할 수 있는 모든 경우의 수를 배열에 저장한다.
2. 경우의 수마다 비용을 계산한다.
   2-1. 이 때 중간에 경로가 끊어진 곳이 있다면 비용을 계산하지 않고 함수를 빠져나온다.
   2-2. 처음 위치로 되돌아 가는 경로가 없다면 마찬가지로 비용을 계산하지 않고 함수를 빠져나온다.
3. 비용 계산이 끝난 후 기존의 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이 크다면 여러가지로 문제를 일으킬 가능성이 있다고 생각했다.

그래서 처음 생각한 방법대로 구현해보기로 했다.

1. 반복문을 돌며 dfs 함수를 호출한다. 이렇게 하면 0에서 출발해서 0으로 돌아오는 경우 부터 n-1에서 출발해서 n-1까지 돌아오는 경우까지 탐색이 가능하다
   2-1. dfs 함수 내에서 반복문을 돌면서 graph의 값이 0이면 continue
   2-2. 만약 0이 아니고 방문한 index가 아니면 sum값에 비용을 더해주고 dfs 재귀호출
2. 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];
            }
        }


    }