외판원 순회(백준_2098)

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

문제 설명

문제에 나와있는데로 외판원 순회 문제는 유명한 문제라고 한다. 하지만 나는 처음 공부해본다 ㅜㅜ

문제는 간단했는데 외판원이 모든 돌 때, 처음 도시로 다시 돌아와야 한다. 이 때 제일 적은 비용을 들이는 여행 계획을 찾는 것이다.

 

문제를 푸는 아이디어

이 문제는 다이나믹 프로그래밍으로 풀어야한다. 거의 모든 곳을 돌면서 최소의 값을 찾아 더해야 한다.

다이나믹 프로그래밍은 언제나 점화식을 잘 세워야 한다. 이게 제일 어려운 것 같다. 

 

점화식 정의

 D[c][v] : 현재 도시가 c, 현재까지 방문한 모든 도시 리스트가 v일 때 앞으로 남은 모든 도시를 경유하는데 필요한 최소 비용이다.

여기서 의문이 드는 점은 v 가 모든 도시 리스트라는 점이다. 어떻게 하나의 변수에 이 도시를 방문 했다는 것을 알 수가 있을까? 바로 이진수를 사용하는 것이다!!

쉽게 4개의 도시가 있다고 하면 1번 도시를 방문 했으면 0001(1), 2번 도시를 방문했으면 0010(2), 2번 3번 도시를 방문했으면 0110(6) 이렇게 만들면 된다. 

 

점화식에 사용한 비트 연산식

이 내용은 Do it! 알고리즘 코딩 테스트를 참고했다.

 

• 모든 도시 순회 판단 연산식

if(v == (1 << N) -1)

1을 N만큼 왼쪽으로 보낸뒤 -1을 하면 최대 숫자가 나온다. 예를 들어 4명이면 10000(2) - 1이므로 15가 나온다. 이것은 모든 도시 방문인 1111과 같다.

 

• 방문 도시 확인 연산식

if((v & (1 << i)) == 0 )

앤드 연산자로 방문 했는지 확인한다. 만약 2번째 도시를 방문 했는지 확인하고 싶을 때, 10 이고  2번째가 1인지 0 인지 확인할 수 있다.

 

• 방문 도시 저장 연산식

v | (1 << i)

이것은 or 연산자로 2번째 도시를 방문 할경우 100으로 v의 2번째를 1 로 만들어 버려 방문 했다는 것을 알리는 것이다.

 

점화식 세우기

c번 도시에서 v 리스트 도시를 방문한 후 남은 모든 도시를 순회 하기 위한 최소 비용은 현재 방문하지 않은 모든 도시를 최소로 방문 할 수 있는 비용을 더하는 것이다.

DP[c][v] = Math.min(D[c][v], (D[i][v] | (1 << i)) + w[c][i])

또 모든 도시를 순회하기 때문에 어떤 도시에서 출발해도 상관이 없다.

 

구현

• Main

public static void main(String []args) throws IOException {
    BufferedReader  buf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(buf.readLine());
    n = Integer.parseInt(st.nextToken());
    dp = new int[16][1<<16];
    w = new int[16][16];
    for(int i=0; i<n; ++i){
        st = new StringTokenizer(buf.readLine());
        for(int j = 0; j<n; ++j){
            w[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    System.out.println(tsp(0,1));
}

이 부분은 Main으로 dp 결과 배열과, 이동 거리 비용 배열인 w를 만들어 준다. 

• tsp

static int tsp(int c, int v){
    //끝까지 도착했을 때
    if(v == (1<<n) -1){
        return w[c][0] == 0 ? INF : w[c][0];
    }
    // 도착한 곳이 이미 도착했던 곳이라면 바로 return
    if(dp[c][v] != 0){
        return dp[c][v];
    }
    
    dp[c][v] = INF;// 최솟값을 찾아야 하므로 지금 값을 최대로 만든다
    for(int i =0; i<n; ++i){
        if((v&(1 << i)) == 0 && w[c][i] != 0){ // 방문하지 않았고 이동할수 있다면 실행
            //재귀로 하나하나 방문해 가면서 최솟값을 넣는다
            dp[c][v] = Math.min(dp[c][v], tsp(i, (v | (1 << i))) + w[c][i]);
        }
    }
    return dp[c][v];
}

https://github.com/Heron-Woong/CodingTest_Practice/commit/8e0526c804f4645b0164ffd857b6e09a2995d22e

백준_2098, 외판원 순회 · Heron-Woong/CodingTest_Practice@8e0526c