[JAVA] 백준 1029 그림 교환

 

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

 

문제분석

이 문제는 예술가들이 하나의 그림을 서로 거래하는 상황에서, 주어진 조건을 만족하며 그림을 소유했던 사람의 수의 최댓값을 구하는 문제이다. 거래는 두 가지 조건을 만족해야 하는데, 첫째는 그림을 팔 때 이전에 산 가격보다 크거나 같은 가격으로 팔아야 하고, 둘째는 같은 사람이 같은 그림을 두 번 이상 살 수 없다는 것이다. 입력으로는 각 예술가가 다른 예술가에게 그림을 살 때의 가격이 주어지며, i번째 줄의 j번째 값은 i번 예술가가 j번 예술가에게 그림을 팔 때의 가격을 의미한다. 처음에는 1번 예술가가 외부 상인에게 가격 0으로 그림을 구매한 상태에서 시작하며, 이후 조건을 만족하는 거래만 이루어진다고 가정했을 때 그림을 소유했던 사람 수의 최댓값을 구해야 한다.

 

이 문제는 단순한 DP처럼 보이지만, 같은 사람이 두 번 이상 그림을 살 수 없다는 조건 때문에 현재까지 그림을 소유했던 사람들의 집합을 상태로 관리해야 한다. 따라서 비트마스크를 이용해 방문 여부를 저장하고, 현재 그림의 소유자와 현재 가격을 함께 상태로 두어 DFS 기반의 메모이제이션 DP를 적용한다. 즉, dp[mask][cur][price]는 현재 상태에서 앞으로 추가로 거래할 수 있는 최대 횟수를 의미하며, 아직 그림을 사지 않았고 가격 조건을 만족하는 예술가에게 그림을 넘기는 모든 경우를 탐색하여 그 중 최대값을 저장한다. 이러한 방식으로 가능한 모든 거래 경로를 탐색하면서도 이미 계산한 상태는 다시 계산하지 않도록 하여 효율적으로 정답을 구할 수 있다.

 

 

코드

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

public class Main {
    static int[][] arr;
    static int[][][] dp;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int[1 << N][N][10]; // dp[bitmask][현재 그림 소유자][그림 구매했던 가격]
        arr = new int[N][N];

        // 산 가격보다 같거나 비싸게 팔아야 함
        // 같은 그림 2번 이상 구매 불가
        for (int i = 0; i < N; i++) {
            // i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에게 그 그림을 살 때의 가격
            // rowIdx : 판매자, colIdx: 구매자
            String[] s = br.readLine().split("");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(s[j]);
            }
        }
        for (int i = 0; i < (1 << N); i++)
            for (int j = 0; j < N; j++)
                Arrays.fill(dp[i][j], -1);
        System.out.println(DFS(1, 0, 0) + 1);
    }

    static int DFS(int bitmask, int cur, int price) { // cur는 현재 그림 소유자, price 는 현재 거래 가격
        if (dp[bitmask][cur][price] != -1)
            return dp[bitmask][cur][price];

        int[] nextPrice = arr[cur];

        int res = 0;
        // 더 내려갈 곳 없으면 아래 for문 안돌음.
        for (int i = 0; i < N; i++) {
            if (nextPrice[i] >= price && (bitmask & (1 << i)) == 0) { // price보다 높으면서, i가 거래하지 않은 사람일 때
                res = Math.max(res, 1 + DFS(bitmask | (1 << i), i, nextPrice[i]));
            }
        }
        dp[bitmask][cur][price] = res;
        return res;
    }
}