SWEA_프로세서연결하기_1767

1. 과정

- 각 코어별 선 연결 방향을 순열로 완탐함 -> 시간초과(8개 통과)

- 가장자리에 있는 코어 제외함 -> 시간초과(25개 통과)

- (최대로 연결된 코어 수 > 현재 연결된 코어 수 + 남은 코어 수) 이 경우 추가 -> 통과(실행시간 : 3,888 ms, 메모리 : 34,804 kb)

- 백트래킹으로 다시 구현 -> 통과(실행시간 : 191 ms, 메모리 : 38,808 kb)

 

 

2. 구현

언어 : JAVA

실행시간 : 3,888 ms

메모리 : 34,804 kb

import java.util.*;

public class SWEA_프로세서연결하기_1767_O {
	static int N, coreNum, answer, maxCore;
	static int[][] map;
	static ArrayList<Core> cores;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static class Core {
		int r, c;

		public Core(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int testCase = 1; testCase <= T; ++testCase) {
			N = sc.nextInt();
			map = new int[N][N];
			answer = Integer.MAX_VALUE;
			cores = new ArrayList<>();
			maxCore = 0;	// 최대로 연결된 코어 수
			coreNum = 0;	// 총 코어 수
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					map[i][j] = sc.nextInt();
					// 가장자리 코어는 제외
					if (i == 0 || j == 0 || i == N - 1 || j == N - 1)
						continue;
					// 코어의 위치를 리스트로 관리
					if (map[i][j] == 1) {
						cores.add(new Core(i, j));
						coreNum++;
					}
				}
			}
			// 현재 코어 인덱스, 연결된 코어 개수, 총 선 연결 길이
			solve(0, 0, 0);
			System.out.println("#" + testCase + " " + answer);
		}
	}

	private static void solve(int idx, int cnt, int len) {
		// 최대로 연결된 코어 수 > 현재 연결된 코어 수 + 남은 코어 수
		if (maxCore > cnt + (coreNum - idx))
			return;

		// 최대로 연결된 코어수 갱신
		if (cnt > maxCore) {
			answer = len;
			maxCore = cnt;
		} 
		// 정답 갱신
		else if (cnt == maxCore) {
			answer = Math.min(answer, len);
		}

		// 코어 수만큼 탐색했으면 return
		if (idx == coreNum)
			return;

		Core core = cores.get(idx);
		int r = core.r;
		int c = core.c;
		// 4방향 탐색
		for (int i = 0; i < 4; ++i) {
			// 연결할 수 있다면 증가 시키고 다음 코어로 ㄱㄱ
			int avail = check(r, c, i);
			if (avail > 0) {
				fillMap(r, c, i, 2);
				solve(idx + 1, cnt + 1, len + avail);
				fillMap(r, c, i, 0);
			}
			// 연결할 수 없다면 상태 유지하고 다음 코어로 ㄱㄱ
			else {
				solve(idx + 1, cnt, len);
			}
		}
	}

	private static void fillMap(int r, int c, int dir, int val) {
		while (true) {
			r += dr[dir];
			c += dc[dir];
			if (r < 0 || c < 0 || r >= N || c >= N)
				return;
			map[r][c] = val;
		}
	}

	private static int check(int r, int c, int dir) {
		int len = 0;
		while (true) {
			r += dr[dir];
			c += dc[dir];
			if (r < 0 || c < 0 || r >= N || c >= N)
				return len;
			else if (map[r][c] != 0)
				return 0;
			len++;
		}
	}

}