BOJ 1102 발전소

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

문제

은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다.

발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다.

적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 값이다. 그 다음 줄에는 각 발전소가 켜져있으면 Y, 꺼져있으면 N이 순서대로 주어진다. 마지막 줄에는 P가 주어진다. 비용은 36보다 작거나 같은 음이 아닌 정수이고, P는 0보다 크거나 같고, N보다 작거나 같은 정수이다.

---

출력

첫째 줄에 문제의 정답을 출력한다. 불가능한 경우에는 -1을 출력한다.

---

예제 입력 1

3
0 10 11
10 0 12
12 13 0
YNN
3

예제 출력 1

21

예제 입력 2

3
0 2 4
2 0 3
4 3 0
YNN
3

예제 출력 2

5

…이하 예제 생략

---

코드

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

public class Main {

    static int N, P, answer = Integer.MAX_VALUE;
    static int[] dp; // 각 발전소의 상태(비트마스크)가 되기 위한 최소 비용을 저장하는 배열
    static int [][] costs;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        costs = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++)
                costs[i][j] = Integer.parseInt(st.nextToken());
        }
        // 초기 발전기의 상태를 입력받는다.
        char[] current = br.readLine().toCharArray();
        int bitmask = 0;
        for (int i = 0; i < current.length; i++) {
            // 발전소가 켜져있으면 비트마스크에서 해당 발전소 위치를 1로 설정
            if(current[i] == 'Y') bitmask |= 1 << i;
        }
        P = Integer.parseInt(br.readLine());

        // 발전소가 켜져있는 게 하나도 없을 때,
        if(bitmask == 0) {
            // P 또한 0이면 최소비용은 0이고, P가 1 이상이면, 불가능한 경우이므로 -1을 출력
            System.out.println(P == 0 ? 0 : -1);
            return;
        }

        dp = new int[1 << N];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[bitmask] = 0; // 초기 발전소 비트마스크에 해당하는 최소 비용은 아무것도 고치지 않았으므로 0
        dfs(bitmask);

        System.out.println(answer);
    }

    static void dfs(int bitmask) {
        /**
         * 만약 현재 상태에서 켜져있는 발전소의 수가 P보다 크거나 같으면,
         * dp에 저장된 현재 상태가 되기까지 드는 최소 비용이 정답이 될 수 있는지 확인
         */
        if(Integer.bitCount(bitmask) >= P) {
            answer = Integer.min(answer, dp[bitmask]);
            return;
        }

        /**
         * 1. 현재 비트마스크에서 꺼져있는 발전소를 찾는다.
         * 2. dp에서 해당 발전소를 켰을 때의 비트마스크에 해당하는 값 (= before)을 기억해둔다.
         * 3. 현재 켜져있는 발전소들로 꺼져있는 해당 발전소를 재시작할 때의 최소 비용을 계산한다.
         * 4. 현재까지의 최소 비용 + 꺼져있는 해당 발전소를 재시작할 때의 최소 비용이
         *    before 보다 작다면, 꺼져있는 해당 발전소를 켰을 때의 비트마스크로 더 탐색을 진행하고
         *    before 보다 크다면, 다음 검사를 진행한다.
         */
        for (int i = 0; i < N; i++) {
            if((bitmask & 1 << i) != 0) continue;

            int newBitmask = bitmask | 1 << i, before = dp[newBitmask];
            for (int j = 0; j < N; j++) {
                if((bitmask & 1 << j) != 0)
                    dp[newBitmask] = Integer.min(dp[newBitmask], dp[bitmask] + costs[j][i]);
            }
            if(before > dp[newBitmask]) dfs(newBitmask);
        }
    }
}