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

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

 

문제 설명 : 

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

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

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

 

입력 :

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

 

출력 : 

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

 

예제 입력 : 

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

 

예제 출력 : 

21

 

 

접근법 : 

1) 어떻게 풀 것인가?

TSP 외판원순회 문제와 거의 판박이다. 

N도 동일하게 16이고, 비트마스킹을 통한 DP 로 O(2^N)을 가지치기 하는 방식으로 풀면 된다.

 

 

dfs 함수는 아래와 같이 구현했다.

cnt : 수리해야하는 발전소 개수      (* 메인함수내에 있는 cnt : 멀쩡하게 돌아가는 발전소 수)

visited : 고장나 있지 않은 발전소 상태

	static int dfs(int cnt, int visited) {
		// 1. 발전소 수리가 끝난 경우
		if (cnt >= P) {
			return 0;
		}

		// 2. 이미 계산한 경우
		if (dp[cnt][visited] != INF) {
			return dp[cnt][visited];
		}

		// 3. 반복문 돌면서 재귀탐색
		for (int i = 0; i < N; i++) {
			// 3-1. 발전소가 켜져 있는 경우
			if ((visited & (1 << i)) != 0) {
				for (int j = 0; j < N; j++) {
					// 3-1-1. 같은 번호의 발전소인 경우 contitnue
					if (i == j) continue;
					// 3-1-2. j도 켜져있는 경우 continue
					if ((visited & (1 << j)) != 0) continue;
					// 최소값 구하기
					dp[cnt][visited] = 
					Math.min(
							dp[cnt][visited], 
							dfs(cnt + 1, visited | (1 << j)) + map[i][j]
					);
				}
			}
		}
		return dp[cnt][visited];
	}

 

전체 코드는 아래 참고.

 

2) 시간복잡도

최악의 경우 N^2 예상되나, DP 가지치기로 무리 없이 통과됨.

(Java 기준 - 800ms)

 

3) 공간복잡도

2^N(16) = 65,536이 크지 않아 고려하지 않음.

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

비트마스킹 DP.

 

Java 코드 : 

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

// 1102 발전소
public class Main {

	static int N, P;
	static int[][] map;
	static int[][] dp;
	static String onOff;

	private static int INF = 987654321;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		int MAX = 1 << N; // 비트 마스킹을 위한 최대치
		dp = new int[N][MAX];

		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
			for (int j = 0; j < MAX; j++) {
				// 초기값 세팅
				dp[i][j] = INF;
			}
		}

		onOff = br.readLine();
		P = Integer.parseInt(br.readLine());

		int cnt = 0;
		int now = 0;
		for (int i = 0; i < N; i++) {
			if (onOff.charAt(i) == 'Y') {
				now = now | (1 << i);
				cnt++;
			}
		}

		int ans = dfs(cnt, now);
		if (ans == INF) {
			ans = -1;
		}

		bw.write(String.valueOf(ans));

		bw.flush();
		bw.close();
		br.close();
	}

	static int dfs(int cnt, int visited) {
		// 1. 발전소 수리가 끝난 경우
		if (cnt >= P) {
			return 0;
		}

		// 2. 이미 계산한 경우
		if (dp[cnt][visited] != INF) {
			return dp[cnt][visited];
		}

		// 3. 반복문 돌면서 재귀탐색
		for (int i = 0; i < N; i++) {
			// 3-1. 발전소가 켜져 있는 경우
			if ((visited & (1 << i)) != 0) {
				for (int j = 0; j < N; j++) {
					// 3-1-1. 같은 번호의 발전소인 경우 contitnue
					if (i == j) continue;
					// 3-1-2. j도 켜져있는 경우 continue
					if ((visited & (1 << j)) != 0) continue;
					// 최소값 구하기
					dp[cnt][visited] = 
					Math.min(
							dp[cnt][visited], 
							dfs(cnt + 1, visited | (1 << j)) + map[i][j]
					);
				}
			}
		}
		return dp[cnt][visited];
	}

}