[SWEA] 1767번 프로세서 연결하기 (JAVA)

SW Expert Academy

일단 Core 중에서도 가장자리에 있는 것들은

전선을 연결하지 않기 때문에

고려해줄 이유가 없으므로 코어의 목록에서 제외하고 시작한다.

 

최대한 많은 Core에 전원을 연결해야 하기 때문에

코어의 개수를 M개라 칭하면,

M개 중 M개를 뽑는 조합부터 시작하여

M - 1, M - 2, ... , 0개를 뽑는 경우까지

차근차근 생각해주어야 한다.

 

M개 중 R개를 뽑는 조합을 구하면,

즉 R개의 Core를 사용할 때,

전선 길이의 합이 최소가 되는 경우를 구해야 한다.

DFS를 사용하여

상, 하, 좌, 우 방향으로 전선을 만들 수 있는지 판단한다.

 

→ 만들 수 있는 경우

재귀로 다음 Core로 넘어가고

최종적으로 모든 Core의 전선의 길이의 합을 구했으면

결과가 될 최솟값에 갱신한다.

R개를 뽑는 모든 조합에 대해 이 과정을 반복한 뒤

최솟값인 결과를 출력하면 된다.

 

→ 만들 수 없는 경우

더 나아가지 못하게 하고 DFS를 빠져나와

다음 조합으로 넘어간다.

R개를 뽑는 모든 조합에 대해 이 과정을 반복한 뒤에도

전선을 만들지 못하는 경우가 나와서 최솟값을 갱신하지 못한다면

R개의 Core를 사용할 수 없다는 뜻이므로

사용할 수 있는 Core의 최대 개수는 R이 아닌 것이다.

그러므로 R - 1개를 뽑는 조합으로 넘어가야 한다.

import java.util.Scanner;

class pair{
	int x, y;
	pair(int x, int y) { this.x = x; this.y = y; }
}

public class SWEA_1767_프로세서_연결하기 {
	private static int T, N, size, min;
	private static int arr[][], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	private static pair core[];
	private static boolean chk[];
	
	public static void combination(int idx, int cnt, int R) {
		if(cnt == R) {
			dfs(0, 0);
			return;
		}
		for(int i = idx; i < size; i++) {
			chk[i] = true;
			combination(i + 1, cnt + 1, R);
			chk[i] = false;
		}
	}
	
	public static void dfs(int idx, int cnt) {
		if(idx == size) {
			min = Math.min(min, cnt); // 배열 끝까지 돌렸으면 이때의 최솟값 갱신
			return;
		}
		if(!chk[idx]) { // 부분 집합에 포함되는 애들만 다음 단계로 넘어갈 수 있다.
			dfs(idx + 1, cnt);
			return;
		}
		for(int i = 0; i < 4; i++) {
			int x = core[idx].x, y = core[idx].y, tmp = 0;
			boolean success = false;
			while(true) {
				x += dx[i]; y += dy[i];
				if(x < 0 || x >= N || y < 0 || y >= N) { // 범위 끝까지 갔으면 성공
					success = true;
					break;
				}
				if(arr[x][y] != 0) break; // 전선이나 코어를 만나면 실패
				arr[x][y] = 2; // 전선 표시
				tmp++; // 전선 길이 합
			}
			if(success) dfs(idx + 1, cnt + tmp);
			while(true) { // 원 상태로 돌려놓기
				x -= dx[i]; y -= dy[i];
				if(x == core[idx].x && y == core[idx].y) break;
				arr[x][y] = 0;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for(int t = 1; t <= T; t++) {
			N = sc.nextInt();
			arr = new int[N][N]; core = new pair[12]; chk = new boolean[12];
			size = 0; min = Integer.MAX_VALUE;
			for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) arr[i][j] = sc.nextInt();
			for(int i = 1; i < N - 1; i++) for(int j = 1; j < N - 1; j++) if(arr[i][j] == 1) core[size++] = new pair(i, j); // 가장자리 빼고
			
			for(int i = size; i >= 0; i--) {
				combination(0, 0, i);
				if(min < Integer.MAX_VALUE) break; // 최솟값이 갱신되어 있으면 결과가 나왔다는 뜻임
			}
			
			System.out.println("#" + t + " " + min);
		}
	}
}