[SWEA / Java] 1767번: 프로세서 연결하기

문제 풀이 날짜: 2023.08.27
포스트 작성일: 2023.08.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

SWEA 1767번: 프로세서 연결하기

 

키워드

백트래킹, 부분 집합

 

풀이 접근법

• 각 코어마다의 전선 방향을 결정하는 순열을 구하는 것이라고 생각하기 쉬운데, 입력이 7 ≤ N ≤ 12 이기 때문에 시간 초과가 난다. 사실상 코어의 순서는 중요하지 않기 때문에 순열을 고려할 필요가 없다.
  • 그럼에도 재귀(백트래킹)로 풀어야 하는 상황인데, 방문하지 않아도 되는 경우에 대해 가지치기를 잘 해주지 않아도 얄짤없이 시간 초과가 난다.
• 그렇다면 어떻게 최적화를 해야하는가?
  • 코어 리스트에 코어를 넣을때, 애초에 연결이 안 되는 코어(벽에 붙은 코어)는 고려하지 않아도 되므로 리스트에 넣지 않는다.
  • 남은 코어를 전부 더해도 현재까지 계산한 maxCore보다 작을 때, 그 이후 탐색을 중단(return)한다. (가지 치기)
    • 즉, 재귀의 최대 depth까지 도달하기 전에 가지치기가 되어야 한다. 가능한 많은 개수의 코어를 연결했을 때의 길이만 필요한데, maxCore를 넘기는 경우를 구하지 못한다면 애초에 그 재귀를 지속할 필요가 없다.

• 부분 집합으로 포함시킬 코어를 정한다. 코어를 선택할 것이라면 4방향으로 연결을 시도(setStatus() 메소드)해보고, 선택하지 않는다면 연결을 시도하지 않고 즉시 다음 재귀로 넘어간다.
  • 모든 전선을 다 놓지 말고, 어떤 방향으로 전선 놓기가 가능한지 판단한 후에 배치가 가능한 전선만 놓는다. 전선을 놓았다면 표시(visit)를 한다.
  • 기저 사례: 부분집합이 완성되었을 때는 연결된 코어의 개수와 최소 길이를 갱신한다.

 

코드

package swea.Ad.swea1767;

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

public class Solution {

	private static int N, totalCount;
	private static int maxCore, minLength;
	
	private static int[] dr = {-1, 1, 0, 0};
	private static int[] dc = {0, 0, -1, 1};
	
	private static int[][] board;
	private static List<Core> cores;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(br.readLine());
			
			totalCount = 0;
			maxCore = 0;
			minLength = Integer.MAX_VALUE;
			
			board = new int[N][N];
			cores = new ArrayList<>();
			
			StringTokenizer st;
			for(int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int j = 0; j < N; j++) {
					board[i][j] = Integer.parseInt(st.nextToken());
					
					if(isBorder(i, j) && board[i][j] == 1) { continue; }
					
					if(board[i][j] == 1) {
						cores.add(new Core(i, j));
						totalCount++;
					}
				}
			}
			
			permutation(0, 0);
			
			sb.append("#").append(test_case).append(" ").append(minLength).append("\n");
		}
		
		System.out.println(sb);
	}

	private static boolean isBorder(int r, int c) {
		return r == 0 || r == N - 1 || c == 0 || c == N - 1;
	}

	/**
	 * @param depth : 재귀의 깊이
	 * @param index : 고려해야 할 코어의 번호
	 * @param coreCount : 지금까지 연결된 코어의 수
	 */
	private static void permutation(int depth, int coreCount) {
		//가지치기: 현재까지 연결된 코어 수 + 남은 코어 수 < 임시 최대 코어 수라면
		//예: 이미 7개짜리 답을 구해놨는데 6개짜리 답밖에 못 구하는 상황이면 가지치기
		if(coreCount + (totalCount - depth) < maxCore) {
			return; 
		}
		
		if(depth == totalCount) {
			int res = getLength();
			
			if(maxCore < coreCount) {
				maxCore = coreCount;
				minLength = res;
			} else if(maxCore == coreCount) {
				minLength = Math.min(res, minLength);
			}
			return;
		}
		
		Core core = cores.get(depth);
		int r = core.row;
		int c = core.col;
		
		//1.현재 코어를 선택
		for(int dir = 0; dir < 4; dir++) {
			if(!isAvailable(r, c, dir)) { continue; }
			
			setStatus(r, c, dir, 2); //전선 놓기
			
			permutation(depth + 1, coreCount + 1);
			
			setStatus(r, c, dir, 0); //전선 지우기
		}
		
		//2.현재 코어를 선택하지 않음
		permutation(depth + 1, coreCount);
	}

	private static int getLength() {
		int len = 0; //전선을 센다.
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(board[i][j] == 2) {
					len++;
				}
			}
		}
		
		return len;
	}

	private static void setStatus(int r, int c, int dir, int status) {
		int nr = r;
		int nc = c;
		
		while(true) {
			nr += dr[dir];
			nc += dc[dir];
			
			if(nr < 0 || nc >= N || nc < 0 || nc >= 0) {
				break;
			}
			
			board[nr][nc] = status;
		}
	}

	private static boolean isAvailable(int r, int c, int dir) {
		int nr = r;
		int nc = c;
		
		while(true) {
			nr += dr[dir];
			nc += dc[dir];
			
			if(nr < 0 || nc >= N || nc < 0 || nc >= 0) { break; }
			
			if(board[nr][nc] != 0) { return false; } //다른 코어를 만나거나 전선이 있다면
		}
		
		return true;
	}
}

class Core {
	int row;
	int col;
	
	public Core(int row, int col) {
		this.row = row;
		this.col = col;
	}
}

---

 

 

git 링크

(git 링크 첨부)