백준 1029 : 그림 교환

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

1029번: 그림 교환

[ 문제풀이 ]

외판원 문제와 비슷한 문제로 모든 경우의 수를 탐색하면 TLE가 발생하지만 비트마스킹 + DP를 활용하여 경우의 수를 탐색하면 해결할 수 있는 문제이다.

dp 테이블을 다음과 같이 정의하자.

dp[i][j] : 현재 방문한 정점의 상태가 i이며 j번째 사람(현재 그림 소유)이 그림을 구매한 비용

 

이렇게 정의한 이유는 방문한 정점의 상태가 같은 상황에서 j번째 사람이 누구에게 그림을 구매하냐에 따라 값이 달라지기 때문이다.

N=5일 때 1-2-3-4-5(5번째 사람이 4번째 사람한테 그림을 구입) 경우와 1-2-4-3-5(5번째 사람이 3번째 사람한테 그림을 구입)하는 경우 구입 금액이 달라질 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int N, max;
	static int[][] map, dp;

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			N = Integer.parseInt(br.readLine());
			map = new int[N + 1][N + 1];
			for (int i = 1; i <= N; ++i) {
				String input = br.readLine();
				for (int j = 1; j <= N; ++j) {
					map[i][j] = input.charAt(j - 1) - '0';
				}
			}
			//dp[i][j] : 현재 방문한 정점의 상태가 i이며 j번째 사람(현재 그림 소유)이 그림을 구매한 비용dp = new int[1 << N][N + 1];
			dfs(1, 1, 1);
			bw.write(max + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static void dfs(int i , int state, int visitCnt) {
		if (max == N) return;
		
		max = Math.max(max, visitCnt);
		if (state == (1 << N) - 1) return;
		
		for (int j = 1; j <= N; ++j) {
			//현재 방문하지 않은 정점이며, 그림을 구매할 수 있다면
			if ((state & (1 << (j - 1))) == 0 && map[i][j] >= dp[state][i]) {
				//방문한 적이 있는데 이미 동일한 상태를 싸거나 같게 구매하였다면 탐색 x
				if (dp[state | (1 << (j - 1))][j] != 0 && dp[state | (1 << (j - 1))][j] <= map[i][j]) continue;
				dp[state | (1 << (j - 1))][j] = map[i][j];
				dfs(j, state | (1 << (j - 1)), visitCnt + 1);
			}
		}
	}
}