외판원 순회(2098)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static int[][] map;
    public static int[][] dp;
    public static int n;
    static final int INF = 987654321;

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        dp = new int[n][(1<<n)-1]; //(1<<n)-1은 이진수로 1111

        //일단 각 간선들의 길이를 표시함
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                int w = Integer.parseInt(st.nextToken());
                map[i][j] = w;
            }
        }

        //dp의 모든 값을 INF로 초기화
        for(int i=0; i<n; i++){
            Arrays.fill(dp[i], -1);
        }

        System.out.println(dfs(0, 1));

        return;
    }

    public static int dfs(int city, int visit){

        //만일 모든 노드를 방문했다면
        if(visit == (1<<n)-1){
            //그럴 일은 없겠지만 마지막 노드와 첫 노드가 연결되있지 않으면 INF(최대값)을 반환
            if(map[city][0] == 0){
                return INF;
            }
            //마지막 노드와 첫 노드를 이어주는 값을 반환
            return map[city][0];
        }

        //만일 해당 루트를 한 번 방문한 적 있다면 해당 루트를 방문했던 값을 반환
        if(dp[city][visit] != -1){
            return dp[city][visit];
        }

        dp[city][visit] = INF;

        for(int i=0; i<n; i++){
            int next = visit | (1<<i); //(1<<i) -> i가 2라면 0100 -> or 연산자를 통해(둘 중 하나만 1이면 1로) 2번째 노드를 방문했다는 표시가 된다.

            if(map[city][i] == 0 || (visit & (1<<i)) != 0){ //만일 길이 없거나 and 연산자를 했을 때(둘 다 1이면 1로) 0이 아니면(새로 갈 도시를 이미 방문했다는 의미)
                continue;
            }

            dp[city][visit] = Math.min(dp[city][visit], dfs(i, next) + map[city][i]); //새로 갈 곳에 현재 값과 새 값을 비교해 더 큰 걸 넣어준다.
        }

        return dp[city][visit]; //해당 위치의 최종 값을 반환
    }
}

깊이 우선 탐색과 함께 dp, 비트마스크를 이용해야 한다.

깊이 우선 탐색만 할 경우 시간초과가 난다.

깊이 우선 탐색으로 푼 코드

/*
    public static void dfs(int index){

        if(index == n){

            long length = 0;
            boolean flag = true;

            for(int i=0; i<n-1; i++){
                if(map[arr[i]][arr[i+1]] != 0){
                    length += map[arr[i]][arr[i+1]];
                }else{
                    flag = false;
                }
            }

            if(flag){
                if(map[arr[n-1]][arr[0]] != 0){
                    length += map[arr[n-1]][arr[0]];
                }

                answer = Math.min(answer, length);
            }


        }

        for(int i=0; i<n; i++){
            //만일 해당 노드를 방문하지 않았다면
            if(visit[i] == false){
                visit[i] = true;
                arr[index] = i;
                index += 1;
                dfs(index);
                visit[i] = false;
                index -= 1;
            }
        }

    }*/