[SWEA] 1767 - 프로세서 연결하기 (자바/Java)

조합을 통해 경우의 수를 한정하는 방법을 자주 사용해야 할 것 같다.

처음에는 그냥 dfs로 풀어서 답은 맞았는데, 시간과 메모리를 너무 많이 잡아 먹었다.

 

지금 생각해보니 필요 없는 경우의 수까지 모두 탐색해서 그런 것 같다.

 

연결하는 코어의 수가 최대여야 하기 때문에, 모든 코어를 연결하는 경우의 수부터 dfs를 진행하고, 만약 그 수의 코어를 연결할 수 없다면 코어의 개수 N 중 N-1개, N-2개를 뽑는 조합을 통해 dfs를 반복하여 결과값이 나올 때까지 계속하면 된다.

 

이런 경우에서는 조합을 활용하는 게 유용한 것 같다.

 

			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
					if (arr[i][j] == 1 && i != 0 && j != 0 && i != N - 1 && j != N - 1)
						cores.add(new int[] { i, j });
				}
			// 입력 끝

			R = cores.size(); // 조합 활용
			check = new boolean[R];
			for (int i = R; i >= 0; i--) {
				comb(0, 0, i);
				if (ans != Integer.MAX_VALUE)
					break; // 갱신되었으면 최대값
			}

벽에 붙어있는 경우는 따로 고려해주지 않아도 되니까 그 경우를 빼고 코어 배열에 추가한다.

코어의 사이즈만큼 check 배열을 만들어서 조합에 포함되었는지 여부를 확인한다.

ans는 처음에 최대값으로 초기화하고, 답을 찾으면 갱신하도록 해서 break조건을 걸어준다.

 

r개를 뽑는 조합의 경우의 수를 구하는 함수다.

해당 index를 포함하는 경우의 수와 포함하지 않는 경우의 수를 갱신해주면서 r개를 뽑으면 connect 함수를 통해 dfs를 한다.

	static void comb(int idx, int cnt, int r) {
		// r개를 뽑는 조합

		if (cnt == r) {
			connect(0, 0);
		}

		for (int i = idx; i < R; i++) {
			check[idx] = true;
			comb(i + 1, cnt + 1, r);
			check[idx] = false;
		}

	}

 

 

 

먼저 core에 있는 모든 idx를 검사하면 값을 return한다.

idx가 core.size가 되었다는 것은 조합에 포함되어 있는 모든 idx에 대해 연결이 성공했다는 것을 의미한다.

조합에 포함된 idx는 연결이 성공한 경우에만 다음 idx를 검사할 수 있기 때문이다.

 

그리고 tmp에 원래의 row, col을 복사해두고 사방탐색을 통해 전선을 연결한다.

while문을 빠져나왔을 때 nr 또는 nc가 배열의 크기를 넘어간 경우에는 벽까지 연결에 성공했다는 뜻이므로, 전선이 지나온 부분을 2로 바꾸고 dfs를 계속한다.

그리고 배열을 다시 원상복구한다.

static void connect(int idx, int line) {
		if (idx == cores.size()) {
			ans = Math.min(ans, line);
			return;
		}
		if (!check[idx])
			connect(idx + 1, line); // 부분집합에 포함되는 애들만 뽑기

		int R = cores.get(idx)[0];
		int C = cores.get(idx)[1]; // core의 좌표

		// 원래 배열 복사하기

		int[][] tmp = new int[N][2];
		for (int i = 0; i < N; i++) {
			tmp[i][0] = arr[R][i];
			tmp[i][1] = arr[i][C];
		}

		for (int d = 0; d < 4; d++) {
			int nr = R + dr[d];
			int nc = C + dc[d];
			while (nr >= 0 && nr < N && nc >= 0 && nc < N && arr[nr][nc] == 0) {
				nr += dr[d];
				nc += dc[d];
			}
			if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
				// 연결됨
				nr -= dr[d];
				nc -= dc[d];
				int dis = Math.abs(R - nr) + Math.abs(C - nc);
				// 배열 채우기
				while (nr != R || nc != C) {
					arr[nr][nc] = 2;
					nr -= dr[d];
					nc -= dc[d];
				}

				connect(idx + 1, line + dis);
				// 배열 원상복구하기
				for (int t = 0; t < N; t++) {
					arr[R][t] = tmp[t][0];
					arr[t][C] = tmp[t][1];
				}
			}

		}

	}

 

전체 코드

package 모의sw;

import java.util.ArrayList;
import java.util.Scanner;

public class SWEA_1767_프로세서 {
	static int N;
	static int[][] arr;
	static ArrayList<int[]> cores;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static int ans;
	static boolean[] check;
	static int R;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			N = sc.nextInt();
			arr = new int[N][N];
			cores = new ArrayList<int[]>();

			ans = Integer.MAX_VALUE; // 코어의 개수
			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
					if (arr[i][j] == 1 && i != 0 && j != 0 && i != N - 1 && j != N - 1)
						cores.add(new int[] { i, j });
				}
			// 입력 끝

			R = cores.size(); // 조합 활용
			check = new boolean[R];
			for (int i = R; i >= 0; i--) {
				comb(0, 0, i);
				if (ans != Integer.MAX_VALUE)
					break; // 갱신되었으면 최대값
			}

			System.out.println("#" + t + " " + ans);

		}

	}

	static void comb(int idx, int cnt, int r) {
		// r개를 뽑는 조합

		if (cnt == r) {
			connect(0, 0);
		}

		for (int i = idx; i < R; i++) {
			check[idx] = true;
			comb(i + 1, cnt + 1, r);
			check[idx] = false;
		}

	}

	static void connect(int idx, int line) {
		if (idx == cores.size()) {
			ans = Math.min(ans, line);
			return;
		}
		if (!check[idx])
			connect(idx + 1, line); // 부분집합에 포함되는 애들만 뽑기

		int R = cores.get(idx)[0];
		int C = cores.get(idx)[1]; // core의 좌표

		// 원래 배열 복사하기

		int[][] tmp = new int[N][2];
		for (int i = 0; i < N; i++) {
			tmp[i][0] = arr[R][i];
			tmp[i][1] = arr[i][C];
		}

		for (int d = 0; d < 4; d++) {
			int nr = R + dr[d];
			int nc = C + dc[d];
			while (nr >= 0 && nr < N && nc >= 0 && nc < N && arr[nr][nc] == 0) {
				nr += dr[d];
				nc += dc[d];
			}
			if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
				// 연결됨
				nr -= dr[d];
				nc -= dc[d];
				int dis = Math.abs(R - nr) + Math.abs(C - nc);
				// 배열 채우기
				while (nr != R || nc != C) {
					arr[nr][nc] = 2;
					nr -= dr[d];
					nc -= dc[d];
				}

				connect(idx + 1, line + dis);
				// 배열 원상복구하기
				for (int t = 0; t < N; t++) {
					arr[R][t] = tmp[t][0];
					arr[t][C] = tmp[t][1];
				}
			}

		}

	}
}