[2098] 외판원 순회

✔ 외판원 순회

[백준 2098]

문제 분석하기

모든 순서를 완전 탐색을 수행

만약 D[i][j]에서 j가 나타내는 것이 현재까지 방문한 모든 도시 리스트라고 할 때,

리스트 데이터를 변수 1개로 저장하기 위해 방문 도시를 이진수로 표현

예) 4번, 1번 방문 

현재 도시가 i이고, 4, 1 도시를 방문한 상태에서 나머지 모든 도시를 경유하는데 필요한 비용을 이진수로 표현 : 1001 → D[i][9]

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[c][v]는 현재 도시가 c, 현재까지 방문한 모든 도시 리스트가 v일 때 앞으로 남은 모든 도시를 경유하는데 필요한 최소 비용
2. 점화식을 구함
   • c번 도시에서 v 리스트 도시를 방문한 후 남은 모든 도시를 순회하기 위한 최소 비용은
     현재 방문하지 않은 모든 도시에 대해 반복하는 것이므로
     D[c][v] = Math.min(D[c][v], D[i][v | (1 << i)] + W[c][i])
   • 이때 W[c][i]는 도시 c에서 도시 i로 가기 위한 비용
3. 점화식으로 D 배열을 채운 후 최솟값을 출력

예) 

W	0	1	2	3
0	0	10	15	20
1	5	0	9	10
2	6	13	0	12
3	8	8	9	0

1번째 방문	2번째 방문	3번째 방문	4번째 방문 (N번째 방문)	시작 도시로 순회	비용
1번 방문 = 1 D[0][1]	1, 2번 방문 = 11 D[1][3] + W[0][1] 1, 3번 방문 = 101 D[2][5] + W[0][2] 1, 4번 방문 = 1001 D[3][9] + W[0][3]	1, 2, 3번 방문 = 111 D[2][7] + W[1][2] 1, 2, 4번 방문 = 1011 D[1][11] + W[1][3] 1, 3, 2번 방문 = 111 D[1][7] + W[2][1] 1, 3, 4번 방문 = 1101 D[3][13] + W[2][3] 1, 4, 2번 방문 = 1011 D[1][11] + W[3][1] 1, 4, 3번 방문 = 1101 D[2][13] + W[3][2]	1, 2, 3, 4번 방문 = 1111 D[3][15] + W[2][3] 1, 2, 4, 3번 방문 = 1111 D[2][15] + W[3][2] 1, 3, 2, 4번 방문 = 1111 D[3][15] + W[1][3] 1, 3, 4, 2번 방문 = 1111 D[1][15] + W[3][1] 1, 4, 2, 3번 방문 = 1111 D[2][15] + W[1][2] 1, 4, 3, 2번 방문 = 111 D[1][15] + W[2][1]	1, 2, 3, 4, 1번 방문 W[3][0] 1, 2, 4, 3, 1번 방문 W[2][0] 1, 3, 2, 4, 1번 방문 W[3][0] 1, 3, 4, 2, 1번 방문 W[1][0] 1, 4, 2, 3, 1번 방문 W[2][0] 1, 4, 3, 2, 1번 방문 W[1][0]	1, 2, 3, 4, 1번 방문 10 + 9 + 12 + 8 = 39 1, 2, 4, 3, 1번 방문 10 + 10 + 9 + 6 = 35 1, 3, 2, 4, 1번 방문 15 + 13 + 10 + 8 = 46 1, 3, 4, 2, 1번 방문 15 + 12 + 8 + 5 = 40 1, 4, 2, 3, 1번 방문 20 + 8 + 9 + 6 = 43 1, 4, 3, 2, 1번 방문 20 + 9 + 13 + 5 = 47

슈도코드 작성하기

N(도시 개수)
W[i][j](i 도시에서 j 도시로 가는데 드는 비용을 저장하는 배열)
D[c][v](현재 도시가 c, 현재까지 방문한 도시 리스트가 v일 때 앞으로 남은 모든 도시를 경유하는데 필요한 최소 비용)
for(i -> 0 ~ N) {
    for(j -> 0 ~ N) {
        W 배열에 값 저장하기
    }
}
tsp(0, 1)
정답 출력하기

tsp(c, v) {
    if(모든 도시를 방문할 때) {
        시작 도시로 돌아갈 수 있을 때 -> return W[c][시작 도시]
        시작 도시로 돌아갈 수 없을 때 -> return 무한대
    }
    if(이미 계산한 적이 있을 때) return D[c][v]
    for(i -> 0 ~ N) {
        if(방문한 적이 없고, 갈 수 있는 도시일 때) {
            D[c][v] = Math.min(D[c][v], tsp(i, (v | (1 << i))) + W[c][i]);
        }
    }
    return D[c][v]
}

코드 구현하기

/**
 * 2098) 외판원_순회
 */
public class D095_2098 {
    static int N;
    static int[][] W;
    static int[][] D;
    static final int INF = 1000000 * 16 + 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N(도시 개수)
        N = Integer.parseInt(br.readLine());
        // W[i][j](i 도시에서 j 도시로 가는데 드는 비용을 저장하는 배열)
        W = new int[16][16];
        // D[c][v](현재 도시가 c, 현재까지 방문한 도시 리스트가 v일 때 앞으로 남은 모든 도시를 경유하는데 필요한 최소 비용)
        D = new int[16][1 << 16];
        // W 배열에 값 저장하기
        StringTokenizer st = null;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 0; j < N; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 정답 출력하기
        System.out.println(tsp(0, 1));
    }

    // 모든 경우의 수와 관련된 완전 탐색과 재귀 구현하기
    private static int tsp(int c, int v) {
        // 모든 도시를 방문할 때
        if (v == (1 << N) - 1)
            // 시작 도시로 돌아갈 수 있을 때 return W[c][시작 도시]
            // 시작 도시로 돌아갈 수 없을 때 return 무한대
            return W[c][0] == 0 ? INF : W[c][0];
        // 이미 계산한 적이 있을 때
        if (D[c][v] != 0)
            // 바로 리턴
            return D[c][v];
        int min = INF;
        for (int i = 0; i < N; i++) {
            // 방문한 적이 없고, 갈 수 있는 도시일 때
            if ((v & (1 << i)) == 0 && W[c][i] != 0) {
                min = Math.min(min, tsp(i, (v | (1 << i))) + W[c][i]);
            }
        }
        D[c][v] = min;
        return D[c][v];
    }
}