[백준 10971] 외판원 순회 2

문제 설명

문제 링크

N개의 도시를 모두 순회할 때 필요한 경비의 최소값을 구하는 문제이다.

• 마지막 도착지에서 끝나는 것이 아니고, 마지막 여행지 -> 처음 출발지로 돌아와야 한다.

각 도시간 이동하는데 드는 비용이 0이라면, 도시간 이동이 불가능함을 나타낸다.

• 즉, 이 경우에는 모든 도시를 순회할 수 없다.

생각 정리

// 함수실행 (파라미터 : 현재 방문하는 도시의 순서, 즉 ?번째인지)

  // N == 현재 방문한 도시의 개수 (N개의 도시를 방문하는 순서가 정해진 상태)
      //경로배열의 마지막에 출발지 추가
      //해당 순서로 이동할 때의 비용 계산 
          //이 때, 0이 나오면 이동이 불가 ==> 
          //모든 도시를 거칠 수 없음 ==> 
          //그냥 리턴하자
      //최소비용을 업데이트한다
      //리턴

  // N개의 도시를 순회하면서 (N개의 도시를 순회하는 순서를 찾아내기 위함)
      //방문을 하지 않았다면
          //방문하고
          //해당 도시를 배열에 추가(=함수의 파라미터로 전달받은 ?번째 여행지에 추가)
          //다음 방문순서를 파라미터로 함수 호출 
          //방문해제

완성

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ10971 {
    static int N, answer = 0;
    static int[][] W;
    static boolean[] visited;
    static int[] path;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        W = new int[N+1][N+1];
        visited = new boolean[N+1];
        path = new int[N+1];

        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        tsp(0);
        System.out.println(answer);
    }

    static void tsp(int curr) {
        if(curr == N) {
            int cost = 0;
            path[N] = path[0]; //출발지로 다시 돌아와야하기 때문에 맨 마지막에 출발지를 넣음
            for(int i=0; i<N; i++) {
                if(W[path[i]][path[i+1]] == 0){
                    return ;
                }
                cost += W[path[i]][path[i+1]];
            }

            if(answer == 0)
                answer = cost;
            else
                answer = Math.min(answer, cost);
            return ;
        }

        for(int i=1; i<=N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                path[curr] = i;
                tsp(curr+1);
                visited[i] = false;
            }
        }
    }
    
}