[백준] 외판원 순회 문제 (10971, 2098, 16991)

 

10971번: 외판원 순회 2 (acmicpc.net)

2098번: 외판원 순회 (acmicpc.net)

16991번: 외판원 순회 3 (acmicpc.net)

16991번: 외판원 순회 3

 

세 문제 다 같은 문제라고 해도 괜찮을 정도로 유사하다 그중 3번을 기준으로 풀이를 적도록 하겠다.

 

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 모든 도시 사이에는 길이 있다. 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

도시 A에서 도시 B로 가는 비용은 두 도시 사이의 거리와 같다. 한 도시 A의 좌표가 (xA, yA), B의 좌표가 (xB, yB)라고 한다면, 두 도시의 거리는 √((xB-xA)2 + (yB-yA)2)와 같다.

도시의 수 N과 모든 도시의 위치가 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 도시의 좌표 x, y가 주어진다. 모든 좌표는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 두 도시의 위치가 같은 경우는 없다.

 

 

내풀이 

 

dfs 으로 해결할 수 있을 듯 하지만 단순한 dfs로 모든 경우의 수를 시도하면 너무 많은 경우의 수에 의해 터져버린다 

결국 모든 도시를 돌아야하는데  N개의 도시를 어떤 순서로 돌아야 최소 비용으로 돌아서 원점으로 돌아올 수 있을까? 라는 문제이기에 

(N-1) * (N-2) * .... * 1  = (N-1)! => O(N!) 시간 복잡도를 갖게 된다.

 

이를 좀 더 효율적으로 하기 위해 dp 와 비트 마스킹을 도입한 dfs로 해결한다고 한다

(백준 골드 상위권 정도 오니깐 그냥 풀 수 있는 문제가 없다 ㅋㅋ... 나같은 평범한 사람은 해결법 보고 반복 연습하는게 답인 것 같다)

 

public static double tsp(int cur, int visit) {

        //다 방문했을 때 마지막 위치에서 원점으로 돌아오는 길이 더하기
        if (visit == visitAll) {
            return edgeTable[cur][0];
        }

        //이미 방문했다면
        if (dp[cur][visit] != 0) {
            return dp[cur][visit];
        }

        dp[cur][visit] = Integer.MAX_VALUE;

        for (int next = 0; next < N; next++) {
            int nextVisit = visit | (1 << next);
            // 방문한적 없고 갈 수 있다면
            if (edgeTable[cur][next] > 0 && (visit & (1 << next)) == 0) {
                dp[cur][visit] = Math.min(dp[cur][visit], tsp(next, nextVisit) + edgeTable[cur][next]);
            }

        }

        return dp[cur][visit];
    }

여기서 핵심은 앞서 말했듯이 보통 visited[] 이런식으로 boolean 배열로 표현하던 현재 방문 상태를 비트 마스킹을 활용하여 표현하여 성능 향상을 이뤄낸 것과 dp 메모제이션이다.

+ 소소하지만 어느 점에서 탐색을 시작해도 똑같은 경로가 나오기에 한번만 하면 된다는 것이다.

 

visitAll = (1 << N) -1 로

예를 들어 N = 5 인 경우 11111 로

각 자릿수가 도시를 방문했는지(1) 안했는지(0) 으로 표현했을 때 모두 방문한 경우를 나타낸다.

=> 모든 도시를 방문했다면 현재의 도시(=마지막 도시)에서 처음 출발한 도시까지의 길이를 더해주어야 하기에 이를 return 한다.

 

두번째 if 문에서는 이미 방문한 곳은 dp에 저장한 값을 바로 가져다 쓰게 한다

 

아니라면 dp 값을 INF 값으로 설정해두고 

for 문을 돌면서 방문한 적 없고 갈 수 있는 곳들을 탐색하며 최소값을 갱신한다.

 

이때  nextVisit = visit | (1 << next) 는  방문을 추가하는 연산 

ex) 00001  (= 초기 상태, 0번 도시에서 출발하는 상태) 에서 4번 도시를 간다고하면 00001 | 10000 = 10001 으로 표현

 

마찬가지로 방문한적 있는지 검사할 때는 10001 에서 다시 4번 도시를 간다고하면 10001 & 10000 = 10000 으로 0 보다 크다

& 연산이 0이 나와야 겹치지 않는, 즉 방문한 적 없는 도시임을 나타내는 것이다.

 

 

소스코드

import java.io.*;
import java.util.*;
public class Main {
    static BufferedReader input;
    static StringBuilder output = new StringBuilder();
    static String src = "4\n" +
            "1 1\n" +
            "2 2\n" +
            "1 2\n" +
            "2 1";

    static int N, map[][], visitAll;
    static double edgeTable[][], dp[][];

    public static void main(String[] args) throws IOException {

        input = new BufferedReader(new InputStreamReader(System.in));
        //input = new BufferedReader(new StringReader(src));
        
        //풀이
        N = Integer.parseInt(input.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer str = new StringTokenizer(input.readLine());
            map[i][0] = Integer.parseInt(str.nextToken());
            map[i][1] = Integer.parseInt(str.nextToken());
        }

        edgeTable = new double[N][N];
        visitAll = (1 << N) - 1;
        dp = new double[N][visitAll];

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int xDiff = Math.abs(map[i][0] - map[j][0]);
                int yDiff = Math.abs(map[i][1] - map[j][1]);
                double length = Math.sqrt(xDiff * xDiff + yDiff * yDiff);
                edgeTable[i][j] = length;
                edgeTable[j][i] = length;
            }
        }

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

    public static double tsp(int cur, int visit) {

        //다 방문했을 때 마지막 위치에서 원점으로 돌아오는 길이 더하기
        if (visit == visitAll) {
            return edgeTable[cur][0];
        }

        //이미 방문했다면
        if (dp[cur][visit] != 0) {
            return dp[cur][visit];
        }

        dp[cur][visit] = Integer.MAX_VALUE;

        for (int next = 0; next < N; next++) {
            int nextVisit = visit | (1 << next);
            // 방문한적 없고 갈 수 있다면
            if (edgeTable[cur][next] > 0 && (visit & (1 << next)) == 0) {
                dp[cur][visit] = Math.min(dp[cur][visit], tsp(next, nextVisit) + edgeTable[cur][next]);
            }

        }

        return dp[cur][visit];
    }
}