[BOJ] 백준 1102번 발전소 (Java)

#1102 발전소

난이도 : 골드 1

유형 : DP/ 비트마스킹

1102번: 발전소

▸ 문제

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이 

비트마스킹을 이용한 DP 풀이 문제이다. 비트마스킹에 익숙하지 않아서 비트마스킹에 대해 뒤적뒤적 공부하며 풀었다.

 

비트마스킹에서 중요한 두 가지 연산이다.

1) num | (1<<i) 

    num에 값을 추가하는 것이다.

     ex) 8 | (1<<2) = 12 으로, 1000 → 1100이 된다.

          발전소로 따지면 (4번 on) -> (4번, 3번 on)으로 바뀐 것이다.

 

   → 비트마스킹 값을 추가해줄 때 많이 사용한다

 

2) num & (1<<i)

    num과 값이 같은 번호만 반환한다.

    ex) 8 & (1<<3) = 8 → 1000 을 반환 (status값이 8일 때, 4번 발전소만 켜져있다는 뜻이다)

         12 & (1<<3) = 8 → 1100 중 값이 일치하는 1000만 반환한다.

          따라서, 12 & ( 1<< i) == (1<<i)라면, i는 현재 상태와 일치하는 값이라는 뜻이다. (현재 상태 : 4,3번 on)

 

   → 비트마스킹 조건문에서 많이 사용한다

 

풀이과정

위 두 가지 비트마스킹 방식을 이해하면 해당 문제는 쉽게 접근할 수 있다.

 

1) 초기에 발전기의 상태를 비트필드를 이용하여 상태 값을 저장한다.

ex) YNN의 경우

      pos : 1 -> 001 (1번 발전소만 켜져있음)

      cnt : 1 -> 현재 작동하고있는 발전기의 갯수로 1개를 count해준다.

int pos =0;
int cnt = 0;
for(int i=0; i<status.length; i++) {
	if(status[i].equals("Y")) {
		pos = pos | (1<<i);
		cnt++;
	}
}

 

 

2) 작동하는 발전기의 갯수가 p와 일치할 때까지 재귀호출 탐색을 반복한다.

ex) pNum : 현재 발전기의 상태 (ex.  1 = 001 = 1번 작동기 on)

     i : 현재 발전기 상태 copy

     j :  i를 제외한 작동하지 않는 새로운 발전기를 찾아 on

 →  p == cnt가 될 때까지 탐색하여 최솟값을 찾아낸다.

static int solve(int cnt, int pNum) {
	if(cnt >= p ) return 0;

	if(dp[cnt][pNum] != -1 ) return dp[cnt][pNum];

	dp[cnt][pNum] = init;
	for(int i=0; i<n; i++) {
		// pNum의 발전소가 켜져있을 때
		if((pNum &(1<<i)) == (1<<i)) {
			for(int j=0; j<n; j++) {
				// 같은 번호의 발전소인 경우 || j도 켜져있는 경우 스킵			
				if((i==j) || (pNum&(1<<j)) == (1<<j)) continue;
				
				//	최소값 구하기 dfs
				dp[cnt][pNum] = Math.min(dp[cnt][pNum], solve(cnt+1, pNum|(1<<j)) + cost[i][j]);
			}
		}
	}
	return dp[cnt][pNum];
}

 

📝 메모 

해당 로직을 풀면서 헷갈렸던 부분을 메모한다.

 

solve(cnt,pos) == dp[cnt][pNum]이라고 가정하고 풀었지만 오류가 계속 발생했다.

cnt = 현재 켜진 발전기 수, pos = 현재 켜진 발전기 번호(bitmask)이다.

solve(cnt,pos)를 돌려서 마지막 리턴값 dp[cnt][pNum]을 받아오게 했다.

 

그래서 난 당연히 solve(cnt,pos) == dp[cnt][pNum]이라고 가정하고 풀었지만 오류가 계속 발생했다.

 

반례는 다음과 같다.

3
0 10 11
10 0 12
12 13 0
NYN
1
→ 이와 같이 최소 켜져야하는 발전기 수는 1개이고 이미 조건이 충족이 되었을 때 반례가 발생한다.

 

한 마디로 처음부터 P값과 Y의 갯수가 일치할 때 발생하는 것이다. 초기에 내가 dp의 모든 값들을 -1로 초기화했다. 그래서 위 반례의 경우에 연산이 필요없으므로 dp[cnt][pNum] = -1이 출력된다.

 

인접행렬의 값을 보면 0도 cost에 해당되어서 답은 0이 되어야 한다.

1 → 1 : 0

2 → 2 : 0

...

n-1 →  n- 1 : 0

 

그래서 if(cnt >= p ) return 0; 을 기저조건에 넣어줌으로써 반례를 해치워버렸다.

 

풀이 코드 

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

public class Main {
	
	static int[][] dp;
	static int[][] cost;
	static int n;
	static int p;
	static int init = 1_023_525_232;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		cost = new int[n][n];
		dp = new int[n+1][1<<16];
		
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				cost[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<n+1; i++) {
			Arrays.fill(dp[i], -1);
		}
		
		String[] status = br.readLine().split("");	
		p = Integer.parseInt(br.readLine());
		
		int pos =0;
		int cnt = 0;
		for(int i=0; i<status.length; i++) {
			if(status[i].equals("Y")) {
				pos = pos | (1<<i);
				cnt++;
			}
		}
		int res = dfs(cnt,pos);
		// dfs(cnt,pos) != dp[cnt][pos]
		// 비용이 0일 때,
		// ex) NYN  p=1 -> 비용은 0인데, dp[cnt][pos] = -1 (맨 첨 초기화 값)이므로 같지 않다.
		// 그래서 if(cnt >= p) return 0; 이 필요하다 
		System.out.println(res == init? -1 : res);		
	}
	
	static int dfs(int cnt, int pNum) {
		if(cnt >= p ) return 0;
		if(dp[cnt][pNum] != -1) return dp[cnt][pNum];
		
		dp[cnt][pNum] = init;
		
		for(int i=0; i<n; i++) {
			// pNum의 발전소가 켜져있을 때
			if((pNum &(1<<i)) == (1<<i)) {
				for(int j=0; j<n; j++) {
					// 같은 번호의 발전소인 경우 || j도 켜져있는 경우 스킵 
					if((i==j) || (pNum&(1<<j)) == (1<<j)) continue;
					
					//최소값 구하기
					dp[cnt][pNum] = Math.min(dp[cnt][pNum], dfs(cnt+1, pNum|(1<<j)) + cost[i][j]);
				}
				
			}
		}
		
		return dp[cnt][pNum];
	}
}

 

비트마스킹을 잘 다룰줄 안다면 여러 알고리즘에서 메모리 사용량도 줄이고 효율적인 코딩이 가능할 것 같다. 주말에 비트마스킹을 능숙하게 다룰 수 있도록 더 공부해봐야겠다!