외판원 순회문제

백준 2098번 문제이다. 비트마스크와 메모이제이션을 활용하여 해결할 수 있다.

문제는 임의의 도시 k에서 시작하여 나머지 도시를 모두 순회한 후 다시 k도시로 돌아가는 거리 중 최소거리를 구하는 것이다. 

1. 처음에는 시작 도시별로 모두 다르게 해야하니 n번 for문을 반복해야하나 싶었는데

1-2-4-3-1

2-4-3-1-2

4-3-1-2-4

3-1-2-4-3

이 4가지 경우의 가중치가 모두 동일함을 알 수 있다(2의 왼쪽은 1, 오른쪽은 4인 것이 다른 경로에도 동일하게 적용됨)

즉 시작 도시를 1로 놓고 풀어도 무방하니 O(N)의 시간복잡도를 없앨 수 있다.

2. 그렇다면 이제 이 문제를 어떻게 작은 문제로 나누는 가에 달려있다. 1번에서 시작하여 순회하는 경우를 생각하자.

1-(2,3,4)-1

여기서 괄호를 아직 방문하지 않은 도시의 부분 집합이라고 생각하자. 밑줄은 현재 방문한 도시이다. 3개의 도시를 방문하는 순서이므로

2,3,4

2,4,3

3,2,4

3,4,2

4,2,3

4,3,2

등 의 순서를 비교해야 할 것이다. 그렇다면 괄호를 더욱 작게 쪼갤 순 없을까?

1-2-(3,4)-1

이렇게 표현하면 현재 2번 도시를 방문하였고 남은 3, 4번 도시를 방문하는 경우의 수가 된다. 마찬가지로

1-2-3-(4)-1

1-2-4-(3)-1

이런 식으로 비교를 하면 최소값을 구할 수 있을 것이다.

그러므로 이 문제는 지금까지 방문한 도시 상태에서 모든 도시를 순회했을때의 최소거리를 구하는 문제로 귀결된다.

3. 그렇다면 방문한 도시의 상태를 어떻게 표시할까? n개의 도시가 있으므로 visited 배열을 생성하여 만들어야될까? 그러기에는 dp에 적용하기 너무 까다롭다. 

하지만 비트마스크를 사용한다면 쉽게 해결할 수 있다.

- 방문한 도시가 없는 경우(N=4)

 0000

- 1번 도시를 방문한 경우

0001

- 2, 4번 도시를 방문한 경우

1010

- 모든 도시를 방문한 경우

1111

여기서 1은 방문, 0은 방문하지 않은 상태를 의미한다.

이를 통해 DP식을 도출해내면

DP[current_city][visited_cities]와 같이 표현할 수 있을 것이다.

예를 들면 1,2,4번 도시를 방문하였고 현재는 4번 도시에 위치한 경우 최소거리를 DP[4][1011(2)=11]로 나타낼 수 있을 것이다.

4. 모든 도시를 방문하는 경우가 base case가 되기 때문에 이를 확인하기 위한 조건이 필요하다.

4개의 도시를 방문하고자 할 때 필요한 비트가 4비트가 될 것이다. 1<<4(left sift 연산을 n번 수행)을 한 것에 -1을 하게 되면 10000-1 = 1111이 되므로, 현재 상태와 비교하여 일치하면 마지막으로 방문한 도시에서 1번 도시까지의 가중치를 반환해주면 되겠다.

특정 도시 k를 방문했는지 확인하고자 한다면 visited_cities&(1<<(k-1))이 0이면 방문하지 않은 상태이며 그렇지 않으면 방문한 상태이다. 이를 통해서 방문했던 도시에 대해서는 재귀를 수행하지 않도록 설계하면 된다.

또한 도시 간에 연결되지 않은 상태는 0으로 표시되어 있으므로 이에 대한 예외처리가 필요하다.

소스코드

  package dp; import java.util.*; import java.io.*; public class P2098 { final static int INF = 987654321; static int[][] w; static int n; static int[][] d; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input/p2098.txt"))); //BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); d = new int[n][1 << n]; w = new int[n][n]; for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < n; j++) { w[i][j] = Integer.parseInt(st.nextToken()); } } for (int i = 0; i < n; i++) { Arrays.fill(d[i], -1); } System.out.println(getDistance(0, 1)); } static int getDistance(int current, int visited) { if (visited == (1 << n) - 1) { return w[current][0]; } if (d[current][visited] >= 0) { return d[current][visited]; } int min = INF; for (int i = 0; i < n; i++) { if ((visited & (1 << i)) == 0 && w[current][i] != 0) { // unvisited int dis = getDistance(i, visited | (1 << i)) + w[current][i]; min = Math.min(dis, min); } } d[current][visited] = min; return d[current][visited]; } }