[BOJ_10971] 외판원 순회 2

설명

---

순열의 형태로 나아갔는데 사실 이런 것을 생각하고 코드를 짜지는 않았다. 솔직히 파악이 힘들어서 다른 블로그의 코드를 1차로 본 후 다시 풀어보았다. 

 

코드에 대한 설명은 아래와 같다.

 

방문 여부 체크는 다시 되돌아가지 않는다는 조건이 있었기 때문에 사용하였고, 최초 출발점인 0로 부터 시작하여 go 함수 내부 for문의 1부터 시작하여 순회를 돌며 갈 수 있는 포인트를 모두 탐색을 진행한다. 그리고, 1(이미 처음 부터 출발지 하나 선택 완료 됌) 부터 카운팅하여 N 개 까지 탐색 했다는 것은 이미 모두 돌았다는 말이니 여기서 부터 돌아갈 수 있는 포인트로 처음 시작 점으로의 가는 비용 더하고 종료하였다.

 

코드

---

package backtracking;

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

public class BOJ_10971 {
    static int N;
    static int w[][];
    static int ans;

    static boolean visited[];
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        N = Integer.parseInt(tk.nextToken());

        w = new int[N][N];

        ans = Integer.MAX_VALUE;



        for(int i = 0; i < N; i++){
            tk = new StringTokenizer(in.readLine()," ");
            for(int j = 0; j < N; j++) {
                w[i][j] = Integer.parseInt(tk.nextToken());
            }
        }
        visited = new boolean[N];
        visited[0] = true;
        go(0, 0, 1);

        System.out.println(ans);

    }
    private static void go(int idx,int sum,int cnt) {
        if(cnt == N && w[0][idx] != 0){
            ans = Math.min(ans, sum + w[0][idx]);
            return;
        }else if(cnt >= N){
            return;
        }
        for(int i = 0; i < N; i++){
            if(!visited[i] && w[i][idx] != 0){
                visited[i] = true;
                go(i,sum + w[i][idx],cnt+1);
                visited[i] = false;
            }
        }
    }
}

10971번: 외판원 순회 2