BOJ 1311 할 일 정하기 1

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

문제

N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다.

사람은 1번부터 N번까지 번호가 매겨져 있으며, 일도 1번부터 N번까지 번호가 매겨져 있다.

$D_{ij}$를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 사람과 일의 수 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 D의 내용이 주어진다. 비용은 10,000보다 작거나 같은 자연수이다.

---

출력

모든 일을 하는데 필요한 비용의 최솟값을 출력한다.

---

예제 입력 1

3
2 3 3
3 2 3
3 3 2

예제 출력 1

6

---

코드

기본적인 접근 방법은 DFS 였고 비트마스킹으로 표현한 메모이제이션을 활용해 쉽게 풀 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, fullBits;
    static int[][] D, dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        fullBits = (1 << N) - 1;
        D = new int[N][N];
        /**
         * dp의 첫 번째 인덱스는 사람의 번호를 의미하고,
         * 두 번째 인덱스는 비트마스크로 표현한 남아있는 일을 의미한다.
         * 즉, dp[i][bitmask]는 i번째 사람이 bitmask 같이 일이 남아있는 상태에서 드는 최소 비용을 의미한다.
         */
        dp = new int[N][1 << N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++)
                D[i][j] = Integer.parseInt(st.nextToken());
        }

        // 첫 번째 사람이 할 일을 선택하지 않았을 때부터 시작
        System.out.println(dfs(0, 0));
    }

    static int dfs(int person, int bitmask) {
        // 모두 각자 할 일을 찾았으면 남은 일이 없으므로 이 때 드는 비용은 0이다.
        if(bitmask == fullBits) return 0;
        if(dp[person][bitmask] != 0) return dp[person][bitmask];

        dp[person][bitmask] = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            // 현재 검사 중인 사람이 i번째 일을 수행했을 때 드는 최소 비용을 계산한다.
            if((bitmask & 1 << i) == 0)
                dp[person][bitmask] = Integer.min(
                        dp[person][bitmask],
                        dfs(person + 1, bitmask | 1 << i) + D[person][i]
                );
        }

        return dp[person][bitmask];
    }
}