백준 - 외판원 순회

코드는 안긴데, TSP 를 이해하는 것이 중요하다. DP에 어떤 값을 기록하는지 생각하자.

 

빠른 해결 방법이 없는 NP 문제 라고 하는데 이 문제가 그렇다.

 

어디에서든 시작해서 N개의 도시를 방문하고 출발지로 다시 돌아오는 최단 거리를 구해야 한다. 두 도시간 거리도 갈 때 올 때 다를 수 있다.

 

이론자체는 간단하다. 현재위치와 이미 방문한 도시를 DP에 저장하여 중복계산하지 않게 해서 시간을 줄인다.

스스로 생각을 못해서 여러 블로그 글을 봐도 이해가 바로 잘 되지 않았는데, 나름 내 자신이 편한 이해방법을 정리해보고자 한다.

 

공통적으로 memory[현재도시][이미방문한도시] 로 2차원 int 배열을 사용하는데,
이미 방문한 도시를 체크하는 방법은 비트마스킹이다.

예를들어 8개 도시라고 (0번 ~7번) 하면 2진수 8개로 처리하는 것이다.

0010 0010  1번, 5번 도시 방문한상태

1100 0001  7번, 6번, 0번 도시 방문한 상태

 

예를 많이 들어야 하는데 5개도시가 있다고 하면

memory[1][11111] : 현재 1번 도시, 모든도시 방문 이니 원래 출발지 도시로 가는 거리 W[1][START_CITY] 값을 가진다.

memory[1][00010] : 현재 1번 도시, 1번도시만 방문한 것으로, 1번도시로 부터 시작하는 우리가 구하고자 하는 값이라고 생각하면 된다. 나의 경우 DP 메모리 기억하는 값을 정할 때, 피보나치를 생각하게되는데, f(3) = f(2) + f(1) 이다 보니, 방문한 곳이 많은 [11111]이 값이 클 것이라고 무의식으로 생각하게 되었는데 반대라서 조금 헷갈렸다. 그걸 확실히 생각하면 쉽게 생각할 수 있을 것이라고 생각한다. 

 

예를 더 들어서, 0 -> 3 -> 2 -> 1 -> 4 -> 0  이라는 순서로 방문하는게 가장 최단거리 정답이라고 가정했을때 

memory[0][00001] 을 결국 찾고 싶은 것이고 (memory[0][00001] 이 정답)

memory[0][00001] = memory[3][01001] + W[0][3] 

memory[3][01001] = memory[2][01101] + W[3][2]

memory[2][01101] = memory[1][01111] + W[2][1]

memory[1][01111] = memory[4][11111] + W[1][4]

memory[4][11111] = W[4][0]

 

이렇게 순서가 되는 것이니 잘 유심히 보고 생각해보면 좋을 것 같다. W[X][Y] 는 X에서 Y가는 거리(비용)를 의미한다.

 

모든 경로를 확인하는 것이니 memory[][] 의 값은 이전과 비교해서 낮은 값이면 갱신해준다.

추가적으로 구현을 하면서 생각할 것은, 이미 방문한 곳인지 체크하는 것, 경로가 존재하지 않는지 체크하는 것이 있다. 그걸 제대로 체크안하면, Stackoverflow가 발생한다. 재귀로 구현하는 특성상 재귀를 빠져나올 방법이 없으면 무한루프에 빠질 수 있으니 유의한다.

 

내용들이 이해갔다면, 코드자체는 짧아서, 금방 이해할 수 있다. 전체코드를 일단 아래에 기술한다.

package gold;

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

/**
 * Baekjoon 2098
 * @link https://www.acmicpc.net/problem/2098
 */
public class TravelingSalesman {
    static int N;
    static int[][] W;
    static int[][] memory;
    static final int MAX = 16000000;
    static final int START_CITY = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        W = new int[N][N];
        memory = new int[N][1 << N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(dfs(START_CITY, 1 << START_CITY));
        br.close();
    }

    private static int dfs(int current, int bitmask) {
        if(memory[current][bitmask] != 0) return memory[current][bitmask];
        if(bitmask == Math.pow(2, N) - 1) return W[current][START_CITY] != 0 ? W[current][START_CITY] : MAX;

        memory[current][bitmask] = MAX;
        //Stream
        IntStream.range(0, N)
                .filter(index -> ((1 << index) & bitmask) == 0 && W[current][index] != 0)
                .forEach(i ->
                        memory[current][bitmask] = Math
                            .min(memory[current][bitmask], dfs(i, bitmask | (1 << i)) + W[current][i])
                );
//        //for grammar
//        for (int i = 0; i < N; i++) {
//            if(((1 << i) & bitmask) == 0 && W[current][i] != 0) {
//                memory[current][bitmask] = Math
//                        .min(memory[current][bitmask], dfs(i, bitmask | (1 << i)) + W[current][i]);
//            }
//        }
        return memory[current][bitmask];
    }
}

 

dfs 메서드의 로직만 간단하게 설명하면 될 것 같은데

재귀로써 계속 불리게 되는 메서드이며,

먼저 memory[current][bitmask] 값이 0이 아니면 (저장값이 있으면) 바로 리턴한다.

그리고 bitmask 가 1111111... 인경우 W[현재위치][시작위치] 를 리턴하되, 0이면(경로가없으면) MAX를 리턴한다.

0 ~ N -1 까지 반복하게 되는데, 방문한 곳이 아니고, 갈수 있는 곳이면 메모리 값을 dfs 재귀 연산과 현재값 중에 최소값으로 갱신하고 리턴한다.

여기서 주의할 것은 비트 쉬프트연산이다.

index 번 도시를 탐색하는 것이고 index번 도시를 방문했는지 체크하는 것은

bitmask 와 1 << index 의 & 연산이다. (쉬프트 좌우를 반대로 쓰거나, 연산결과를 0이 아니거나 혹은 0이 아닌 숫자를 써서 작성하면 논리 오류이다. 

memory를 갱신하는 부분은 bitmask 가 1로 채워질수록 값이 커지는 것이 아니라 그 반대라는 개념을 잘 생각하면, 이해하기 어렵지 않을 것이라 생각한다.

실수한 점 

못가는 거리를 Integer.MAX 로 지정하니 dfs에서 값을 합산할 때, (-) 값을 가지는데 이걸 위해 개별 처리하는

것이 더 로직적으로 손해라고 생각하여, 문제에 주어진 로직 상 갖는 한계값 16,000,000 을 MAX 로 지정하였다.

 

또 Memory에 max값을 넣는 것을 전체 초기화 해주는 과정을 처음헤 했더니, 시간초과가 발생하였다. 2차원 배열을 전체 Arrays.fill() 하는 것이 얼마나 시간이 많이 걸리는지 알 수 있었다.