Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

33. 동적 계획법3

비트마스크를 배우고, 동적 계획법에 적용해 봅시다. 그 후에는 선형이 아니라 원형으로 구성된 문제를 다룹니다.

Java / Python

3. 외판원 순회

2098번

비트마스크 DP를 이용하여 최소 비용으로 모든 도시를 순회하는 문제

이번 문제는 N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 문제이다. 외판원 순회 문제는 TSP(Traveling Salesman Problem)라고도 하며, 비트 마스크를 dp를 사용할 때 어떻게 활용할 수 있는지 알 수 있는 문제이다. 즉, 비트마스크를 이용한 동적 프로그래밍 + dfs 방법으로 풀 수 있는 문제이다.

dfs 함수(현재 노드, 현재까지 방문한 도시 정보)를 비트마스크로 전달하며 이용하며 1번도시부터 도시들을 하나씩 방문해 나간다. 예를 들어, 1,2,3,4번 도시를 모두 방문하고 나면, visit은 1111(2)가 되며, 더 이상 방문할 도시가 없게 되어 재귀를 탈출한다. 마지막 도시에서 다시 시작 도시(1번)로 가야 하므로 현재 도시와 1번 도시 사이의 경로의 비용을 반환하는 이러한 방식으로 구현할 수 있다.

비트마스크 : 비트의 형태를 활용하는, 알고리즘보다는 테크닉 중 하나로써, 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. 수행 시간이 빠르고, 코드가 짧으며 메모리 사용량이 더 적다는 장점이 있다.

• Java

점화식 :
dp[node][visit] = min(dp[node][visit], dp[i][visit | (1 << i)] + W[node][i])

import java.util.*;
import java.io.*;

public class Main {
	static final int INF = 16000000;
	static int N; // 도시의 수
	static int[][] W, dp; // W:비용 행렬

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		W = new int[N][N];
		dp = new int[N][(1 << N) - 1];

		for (int i = 0; i < N; i++)
			Arrays.fill(dp[i], INF);

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int cost = Integer.parseInt(st.nextToken());
				W[i][j] = cost;
			}
		}

		bw.write(dfs(0, 1) + "\n");

		bw.flush();
		bw.close();
		br.close();
	}

	public static int dfs(int node, int visit) {

		if (visit == (1 << N) - 1) {	// 모든 지점 방문
			if (W[node][0] == 0)
				return INF;
			return W[node][0];
		}

		if (dp[node][visit] != INF) {	// 이미 계산
			return dp[node][visit];
		}

		for (int i = 0; i < N; i++) {
			if ((visit & (1 << i)) == 0 && W[node][i] != 0) { // 방문한 적 없음
				dp[node][visit] = Math.min(dp[node][visit], dfs(i, visit | (1 << i)) + W[node][i]);
			}
		}

		return dp[node][visit];
	}
}

• Python

import sys
input = sys.stdin.readline
N = int(input())

def tps(n, v):
    if dp[n][v] is not None:
        return dp[n][v]

    result = 10**9
    for i in range(N - 1):
        if i != v and n & (1 << i):
            tmp = tps(n - (1 << v), i) + w[i][v]
            if tmp < result:
                result = tmp
    dp[n][v] = result
    return result

w = [list(map(lambda x: int(x) if x != "0" else 10**9, input().split())) for _ in range(N)]
dp = [[None] * (N - 1) for _ in range(1 << N - 1)]
for i in range(N - 1):
    dp[1 << i][i] = w[-1][i]
print(min(tps((1 << N - 1) - 1, i) + w[i][-1] for i in range(N - 1)))