[백준]JAVA - 1102번: 발전소

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

1102번: 발전소

 

🔶 풀이

비트마스킹 dp.

 

이 문제를 해결하기 위해서 비트마스크를 공부했다.

공부 내용은 추후에 올릴 예정✌️

 

2023.04.17 추가

- 비트마스크 참고 포스팅

 

비트마스크에서 흔히 사용하는 연산은 두 가지다.

1. num | (1 << K) : num에 값을 추가.

  ex) 0 | (1 << 2) = 4, 000 -> 100

 

2. num & (1 << K) : num과 같은 번호를 반환 (포함하고 있다는 의미)

  ex) 0 & (1 << 2) = 0, 포함하고 있지 않음 → 발전소가 고장남

        4 & (1 << 2) = 4, 포함하고 있음 → 발전소가 정상 작동 중

 

위 내용만 알면 해당 문제는 해결할 수 있다.

 

초기 발전기 상태를 1번 내용(비트필드)를 이용해서 값을 저장한다.

int pos = 0; // 현재 발전소 작동 상태 (ex. YNN -> 001)
int cnt = 0; // 현재 작동하고 있는 발전소 개수

String str = br.readLine();
for (int i=0; i<N; i++) {
    if (str.charAt(i) == 'Y') {
        pos = pos | (1 << i); // (ex. 001 -> 100)
        cnt++;
    }
}

pos 변수에는 현재 발전소의 상태를 저장해주고, cnt 변수에는 정상 작동하고 있는 발전소의 개수를 입력한다.

 

2번 내용은 재귀호출 탐색을 진행할 때 활용해주면 된다.

static int dfs (int cnt, int pos) {
    if(cnt >= P) return 0;
    if(dp[pos] != -1) return dp[pos];

    dp[pos] = Integer.MAX_VALUE;

    for(int i = 0; i < N; i++) {
        
        // i번째 발전소가 정상 작동하는 경우
        if((pos & (1 << i)) != 0) {
            for(int j = 0; j < N; j++) {
                
                // j번째 발전소가 고장난 경우
                if((pos & (1 << j)) == 0) {
                    dp[pos] = Math.min(dp[pos], dfs(cnt + 1, pos | (1 << j)) + cost[i][j]);
                }
            }
        } 
    }
    return dp[pos];
}

pos & (1 << i)의 값이 0 이상이라면 값을 포함하고 있다는 뜻이다. 즉, 정상 작동하고 있다는 의미를 가진다.

 

✅ 예외 처리

1. 정상 작동 중인 발전소 개수(N)가 0이고, 목표 개수(P)도 0이면 답은 0이다.

2. 정상 작동 중인 발전소 개수(N)가 0이고, 목표 개수(P)가 1이상이면 답은 -1이다. (불가능)

 

 

<최종코드>

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

public class Main {
    static int dp[], cost[][];
    static int N, P;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        N = Integer.parseInt(br.readLine()); // 발전소 개수
        cost = new int[N][N];
		
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }
		
        // dp 배열 -1로 채우기
        dp = new int[1 << N];
        Arrays.fill(dp, -1);
		
        int pos = 0; // 현재 발전소 작동 상태 (ex. YNN -> 001)
        int cnt = 0; // 현재 작동하고 있는 발전소 개수
		
        String str = br.readLine();
        for (int i=0; i<N; i++) {
            if (str.charAt(i) == 'Y') {
                pos = pos | (1 << i); // (ex. 001 -> 100)
                cnt++;
            }
        }
        
        P = Integer.parseInt(br.readLine()); // 목표 수리 발전소 개수
        
        int ans = findMinimumCost(cnt, pos);
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
	
    static int dfs (int cnt, int pos) {
        if(cnt >= P) return 0;
        if(dp[pos] != -1) return dp[pos];

        dp[pos] = Integer.MAX_VALUE;

        for(int i = 0; i < N; i++) {
        
            // i번째 발전소가 정상 작동하는 경우
            if((pos & (1 << i)) != 0) {
                for(int j = 0; j < N; j++) {
                
                    // j번째 발전소가 고장난 경우
                    if((pos & (1 << j)) == 0) {
                        dp[pos] = Math.min(dp[pos], dfs(cnt + 1, pos | (1 << j)) + cost[i][j]);
                    }
                }
            } 
        }
        return dp[pos];
    }
}