[백준] 10971번 : 외판원 순회 2 - JAVA [자바]

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

---

dfs 문제이다.

N개의 도시를 중복되지 않게 순열을 만든다고 생각하면 된다.

순열을 만들 때 생각해야 하는 것이 몇가지 있다.

1. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j] = 0이라고 하자.
2. 초기의 최소 값을 뭐로 할지

dfs 코드 일부분을 보면서 먼저 1 번부터 생각해보자.

for (int i = 0; i < N; i++) {
	// 아직 방문하지 않은 도시이다.
	if (!visited[i]) {
		// 현재 처음 방문한 도시가 아니라면
		if (depth > 0) {
        	// 전에 방문한 도시에서 지금 i 번째 도시로 올 수 있는지 본다
    		if (costArr[cityArr[depth - 1]][i] == 0) continue;
		}
    	visited[i] = true;
    	cityArr[depth] = i;
    	dfs(depth + 1);
    	visited[i] = false;
    }
}

if (!visited[i]) : 아직 방문하지 않은 도시이다.

현재 처음 도시가 아니라면 (depth != 0)
전에 갔던 도시(cityArr[depth - 1]) 에서 현재 갈 도시 i로 가는 비용을 본다.
비용이 0이라면 갈 수 없으므로 i 를 건너뛰고 다음 도시로 continue 한다.

이렇게만 처리하면 다 될줄 알았는데, 이렇게 처리하면 예외 상황이 한가지 있다.
바로 마지막 도시에서 처음 도시로 돌아올 때 처리를 못한 것이다.

다시 코드로 경로가 다 만들어졌을 때 정답을 판별하는 dfs 알고리즘의 일부분을 보자

// N 개의 도시를 다 방문했다.
if (depth == N) {
	// 만들어진 경로의 비용을 확인한다.
	int cost = 0;
    // 처음도시부터 마지막 도시까지 가는 비용을 모두 더한다.
    for (int i = 0; i < N - 1; i++) {
    	cost += costArr[cityArr[i]][cityArr[i + 1]];
	}
    // 여기서 마지막 도시에서 처음 도시로 돌아올 때의 비용이 0인지 확인한다.
    // 0이면 갈 수 없는 경로이므로 바로 return 한다.
    if (costArr[cityArr[N - 1]][cityArr[0]] == 0) return;
    // 0이 아니면 마지막에서 처음으로 돌아오는 비용도 더해주고
    // 현재 구해진 최소값보다 작은지 확인하여 업데이트 한다.
    cost += costArr[cityArr[N - 1]][cityArr[0]];
    MIN = Math.min(cost, MIN);
    return;
}

마지막에서 처음 도시로 돌아올 때의 비용을 확인하여 올바른 경로인지 확인하고 올바르지 않으면 바로 return한다.

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class bj10971 {

    public static int N;
    public static int[] cityArr;
    public static boolean[] visited;
    public static long MIN;
    public static int[][] costArr;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N];
        cityArr = new int[N];
        costArr = new int[N][N];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            for (int j = 0; j < N; j++) {
                costArr[i][j] = Integer.parseInt(split[j]);
                MIN += costArr[i][j];
            }
        }

        dfs(0);

        bw.write(MIN + "");

        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int depth) {
        // N 개의 도시를 다 방문했다.
        if (depth == N) {
            // 만들어진 경로의 비용을 확인한다.
            int cost = 0;
            // 처음도시부터 마지막 도시까지 가는 비용을 모두 더한다.
            for (int i = 0; i < N - 1; i++) {
                cost += costArr[cityArr[i]][cityArr[i + 1]];
            }
            // 여기서 마지막 도시에서 처음 도시로 돌아올 때의 비용이 0인지 확인한다.
            // 0이면 갈 수 없는 경로이므로 바로 return 한다.
            if (costArr[cityArr[N - 1]][cityArr[0]] == 0) return;
            // 0이 아니면 마지막에서 처음으로 돌아오는 비용도 더해주고
            // 현재 구해진 최소값보다 작은지 확인하여 업데이트 한다.
            cost += costArr[cityArr[N - 1]][cityArr[0]];
            MIN = Math.min(cost, MIN);
            return;
        }
        for (int i = 0; i < N; i++) {
            // 아직 방문하지 않은 도시이다.
            if (!visited[i]) {
                // 현재 처음 방문한 도시가 아니라면
                if (depth > 0) {
                    // 전에 방문한 도시에서 지금 i 번째 도시로 올 수 있는지 본다
                    if (costArr[cityArr[depth - 1]][i] == 0) continue;
                }
            	visited[i] = true;
            	cityArr[depth] = i;
            	dfs(depth + 1);
            	visited[i] = false;
            }
        }
    }
}

못가는 경로를 잘 생각해서 예외 처리를 해줘야 한다.