[백준] 외판원 순회2 (자바)

외판원 순회2

문제풀이

N개의 도시들이 존재하고,
각 도시를 연결하는 경로에 비용 값이 존재하는 문제입니다.

따라서 단순한 dfs 문제에서 조금 더 생각을 요구하는 문제입니다.

도시를 움직이면서 드는 최소한의 비용을 찾아야 하는 문제이므로 도시를 완주하는 경로들을 탐색하여 비용 값을 memoization 했다가 최소인지 확인하는 과정이 필요합니다.

저는 DFS 방식을 이용해서 구현을 했습니다.

DFS method 매개변수에는 시작하는 도시 start, 현재 위치의 도시 now, 현재까지의 총 비용 sum, 몇 개의 도시를 돌았는지 확인하는 depth가 있습니다.

기존의 dfs 방식과 유사하게 코드를 짜는 대신에 dfs 내 반복문에 visit를 true로 표시한 뒤 재귀를 한 뒤에 visit를 다시 false로 변경해서 모든 경로들을 다 확인할 수 있도록 설정했습니다. 그리고 위에는 만약 도시들을 다 돌았다면 비용값의 최소값을 비교하는 코드를 작성했습니다.

구현코드

import java.io.*;
import java.util.*;

import java.lang.*;

public class Main{
    static int num;
    static int[][] arr;
    static boolean[] visit;
    static int cost;

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

        StringTokenizer st;

        // 1번부터 N번까지 번호가 매겨져 있는 도시들, 도시들 사이에 길이 있다
        // 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐
        // 다시 원래의 도시로 돌아오는 순회 여행 경로 계획
        // 단 한 번 갔던 도시로는 다시 갈 수 없다

        // 도시의 수
        num = Integer.parseInt(br.readLine());

        arr = new int[num][num];

        cost = Integer.MAX_VALUE;
        visit = new boolean[num];

        // 다음 N개의 줄에는 비용 행렬이 주어짐
        for (int i = 0; i<num; i++){
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j<num; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < num; i++){
            visit[i] = true;
            dfs(i,i,0,0);

        }

        bw.write(cost+"");
        bw.flush();
        br.close();
        bw.close();
    }

    public static void dfs(int start, int now, int sum, int depth){
        if (depth == num - 1){
            if (arr[now][start] != 0){
                sum += arr[now][start];
                cost = Math.min(cost, sum);
            }
            return;
        }

        for (int i = 0; i < num; i++){
            if (!visit[i] && arr[now][i] != 0){
                visit[i] = true;
                dfs(start, i,sum+arr[now][i],depth+1);
                visit[i] = false;
            }
        }

    }

}