[백준] 1029번 그림 교환 (Java)

문제는 다음과 같다.

백준 1029번 문제 바로가기

DFS, 비트 마스킹, DP(memorization)를 활용한 해결

방문했던 노드(그림을 소유 했던 사람들)을 습관적으로 isvisit 라는 리스트를 활용해 유연하게 함수를 다루지 못했다. 첫 번째로 제출한 코드는 시간초과였다.

• 재귀를 통해 DFS 탐색
• 가격이 지금보다 높거나 같다면 구매하고, 최댓값 업데이트
• 위 과정을 반복해 최댓값을 반환

시간 초과를 해결할 수 있는 방법에 대해 고민하는 과정이 제일 어려웠다. DFS 탐색을 해야 하는 것은 자명했고, 결국 DP를 활용하는 방법밖에 보이지 않았다. DP를 활용해 현재 방문한 노드(그림을 소유한 사람)와 지금까지 방문했던 노드 그리고 구매한 가격을 기준으로 cache 테이블을 만들 수 있었다. 지금까지 방문한 노드를 리스트로 표현하면, cache 테이블을 만들 수 없었다. 그래서 활용한 것이 비트 마스킹이다.

• 재귀를 통해 DFS 탐색
• DP 리스트에 값이 존재한다면 반환
• 가격이 지금보다 높거나 같다면 구매하고, 최댓값 업데이트
• 위 과정을 반복하고 최댓값 DP 리스트에 업데이트
• 최댓값 반환

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int [][] wList;
    static int[][][] dpList;
    static int dfs(int visited, int price, int from, int sum, int n)
    {
        int res = sum;
        int compSum;
        if (dpList[from][visited][price] != 0)
        {
            return dpList[from][visited][price];
        }
        for (int i = 0; i < n; i++)
        {
            // 실수했던 부분 visited는 wList와 순서를 반대로 부여했음을 잊지 말자
            if ((visited | (1 << i)) != visited  & price <= wList[from][n - 1 - i]) // 실수했던 부분 visited는 wList와
            {
                if (res < (compSum = dfs(visited | (1 << i), wList[from][n  - 1 - i], n - 1 - i, sum + 1, n)))
                {
                    res = compSum;
                }
            }
        }
        dpList[from][visited][price] = res;
        return res;
    }

    public static void main(String[] args) {

        int n;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try
        {
            n = Integer.parseInt(br.readLine());
            wList = new int[n][n];
            dpList = new int[n][1 << n][10];
            for (int i = 0; i < n; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    wList[i][j] = br.read() - '0';
                }
                br.read();      // 개행문자를 넘기기 위한 read()
            }
            System.out.println(dfs(1 << (n - 1), 0, 0, 1, n));
        }catch (Exception e)
        {
            e.printStackTrace();
        }
    }
}