[알고리즘] Java / SWEA / 프로세서 연결하기 / 1767

[알고리즘] Java / SWEA / 프로세서 연결하기 / 1767

문제

문제 링크

접근 방식

1. 코어의 행, 열 좌표와 탐색할 수 있는 방향 리스트를 가진 코어 클래스를 생성한다
2. 테두리에 있지 않은 코어를 찾아 코어 리스트에 저장한다
3. 각 코어를 4방향 탐색하여 전선을 설치 할 수 있는지 확인하고, 전선을 설치할 수 있는 경우 해당 코어의 방향 리스트에 방향을 저장한다(0,1,2,3). 추가로 연결하지 않는다는 뜻인 4도 저장한다
4. 중복순열로 코어리스트에 있는 코어들 수 만큼 코어의 방향을 정하는데 이 때 각 코어들의 방향 리스트에서 방향을 선택한다.
5. 이전에 연결했던 코어 수보다 현재 연결할 수 있는 코어 수가 적다면 가지치기한다
6. 전선을 깔면서 전선수를 세고 정상적으로 깔렸다면 전선 최소 수를 갱신한다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution_1767_정현명 {

	public static class Core{
		int r;
		int c;
		List<Integer> search;
		Core(int r, int c){
			this.r = r;
			this.c = c;
			this.search = new ArrayList<>();
		}
	}
	
	
	static int[] numbers;
	static int[][] map;
	static List<Core> coreList;
	static int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};
	static int N;
	static int minWireCnt;
	static int maxCoreCnt;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;		
		
		for(int tc=1;tc<=T;tc++) {
			N = Integer.parseInt(br.readLine());
			
			map = new int[N][N];
			coreList = new ArrayList<>();
			minWireCnt = Integer.MAX_VALUE; // 전선 최소 수
			maxCoreCnt = 0; // 연결된 코어 최대 수
			
			// 맵 입력 받기 
			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());
					// 가장자리가 아닌 코어를 코어리스트에 넣기 
					if(map[i][j] == 1 && i>0 && j>0 && i<N-1 && j < N-1) {
						coreList.add(new Core(i,j));
					}
				}
			}
			
			// 각 코어의 네 방향을 탐색하여 전선을 깔 수 있는지 확인
			// 전선 깔 수 있으면 객체의 search에 추가 (0 : 위, 1 : 오, 2 : 아, 3 : 왼, 4 : 설치 x)
			for(int i=0;i<coreList.size();i++) {
				Core core = coreList.get(i);
				
				loop:for(int j=0;j<4;j++) {
					int r = core.r + deltas[j][0];
					int c = core.c + deltas[j][1];
					
					while(r >= 0 && r< N && c>= 0 && c< N) {
						if(map[r][c] != 0) continue loop;
						r += deltas[j][0];
						c += deltas[j][1];
					}
					core.search.add(j);
				}
				core.search.add(4);
			}
			
			
			numbers = new int[coreList.size()];
			
			permuRep(0,coreList.size());
			
			sb.append("#"+tc+" "+minWireCnt+"\n");
			
		}
		System.out.println(sb);
		
	}
	
	public static void permuRep(int cnt, int target) {
		if(cnt == target) {
			// 현재 연결할 수 있는 코어를 센다
			int realCore = 0;
			for(int i=0;i<numbers.length;i++) {
				if(numbers[i] != 4) realCore++;
			}
			
			// 이전에 연결했던 코어 수보다 현재 연결할 수 있는 코어수가 크거나 같을 경우에만 전선 깔기 시작
			if(realCore >= maxCoreCnt) wireInstall(numbers.clone());
			
			return;
		}
		
		// 각 코어가 탐색할 수 있는 방향만 중복 순열로 선택
		Core core = coreList.get(cnt);
		for(int i=0;i<core.search.size();i++) {
			numbers[cnt] = core.search.get(i);
			permuRep(cnt+1,target);
		}
		
	}
	
	// 전선 깔기
	public static void wireInstall(int[] coreOrder) {
		// 2차원 깊은복사.. 이것 때문에 계속 삽질...
		// 2차원 배열을 그대로 clone하면 그 안의 1차원 배열들 주소는 그대로이기 때문에 오류 발생
		int[][] subMap = new int[N][N];
		for(int i=0;i<N;i++) {
			subMap[i] = map[i].clone();
		}
		
		int cnt = 0;
		int coreCnt = 0;
		for(int i=0;i<coreList.size();i++) {
			Core core = coreList.get(i);
			
			int o = coreOrder[i];
			if(o == 4) continue; // 전선깔지 않기 
			coreCnt++;
			
			int r = core.r + deltas[o][0];
			int c = core.c + deltas[o][1];
			
			while(r >= 0 && r< N && c>= 0 && c< N) {
				if(subMap[r][c] != 0) return;
				subMap[r][c] = 2;
				cnt++;
				r += deltas[o][0];
				c += deltas[o][1];
			}
			
		}

		// 이전보다 코어가 연결된 경우, 혹은 이전과 동일하게 코어가 연결되었고 전선 수가 이전보다 적을 때 갱신
		if(maxCoreCnt < coreCnt || (maxCoreCnt == coreCnt && minWireCnt > cnt)) {
			minWireCnt = cnt;
			maxCoreCnt = coreCnt;
		}
		
	}
	
}