[코드트리/INTERMEDIATE LOW] 외판원 순회 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 백트래킹 (중복 없는 순열)

. 중복 없는 순열을 구하듯이 1에서부터 n개를 뽑는 백트래킹을 진행한다. (→ 방문 표시 배열 사용)

. 1에서부터 백트래킹을 시도하기 전 방문 배열의 1은 방문 처리하고, 리스트에도 1은 미리 추가해둔다.

- 시간 복잡도 : O(N! *N)

 

 

💥 유의사항

- 마지막 지점에서 뽑으려는 지점 간 이동 가능해야(= 비용이 0이 아니어야) 이동 가능하다.

- 1번 지점으로 돌아오는 처리를 꼭 해야 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int n;
    static int[][] A;
    static boolean[] visited;
    static List<Integer> list = new ArrayList<>();
    static int min = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        n = Integer.parseInt(br.readLine());
        A = new int[n+1][n+1];
        visited = new boolean[n+1];
 
        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= n ; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        visited[1] = true;
        list.add(1);
        solve(1);
 
        System.out.println(min);
    }
 
    private static void solve(int cnt) {
        if(cnt == n) {
            if(A[list.get(cnt - 1)][1] != 0)    // 🔔 마지막 지점과 1번 지점까지 이동할 수 있는 경우에만 거리 구함
                min = Math.min(min, getSum());
            return;
        }
 
        for(int i = 1 ; i <= n ; i++) {
            if(!visited[i] && A[list.get(cnt - 1)][i] != 0) {    // 사용한 적 없고, 마지막 지점과 선택할 지점 간 이동이 가능한 경우 탐색 진행
                visited[i] = true;
                list.add(i);
 
                solve(cnt + 1);
 
                visited[i] = false;
                list.remove(list.size() - 1);
            }
        }        
    }
 
    private static int getSum() {
        int sum = 0;
 
        for(int i = 0 ; i < list.size() - 1 ; i++) {
            sum += A[list.get(i)][list.get(i + 1)];
        }
        sum += A[list.get(list.size() - 1)][1];    // 마지막 지점과 1번 지점 간 비용도 추가
 
        return sum;
    }
}

 

 

 

➕ 다른 풀이 방식

방문할 지점 선택은 그대로 하고, 모든 지점을 방문했을 때 해당 두 지점 간 비용이 0인 경우가 있다면, 최솟값을 구하지 않고 바로 return해 종료하게 할 수도 있다.

 

---

💦 어려웠던 점

50분 소요..

문제를 제대로 안 읽어서 이동 중인 두 점과 마지막 점과 1 간 이동할 수 없는 경우(0)면 이동하지 못 하게 하는 조건 처리를 생각하지 못 했다.

 

 

1회독	2회독	3회독	4회독	5회독
V