[SWEA] 1767. [SW Test 샘플문제] 프로세서 연결하기

 

[SWEA] 1767. [SW Test 샘플문제] 프로세서 연결하기

 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf&categoryId=AV4suNtaXFEDFAUf&categoryType=CODE&problemTitle=1767&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&

SW Expert Academy

 

1. 가장 자리 코어는 배제시킨다. 예시에서는 5개의 코어를 담는 리스트를 만든다.

2. 어떤 코어를 선택하여 연결하느냐가 연결에 영향을 미치며, 순서는 상관없기 때문에 조합 문제이다.
 2-1. 5개의 코어 중 1개를 택할 때 (5C1)부터 5개 모두를 택할 때 (5C5) 모두 해보아야 한다. 즉 공집합을 제외한 모든 경우를 세어 보아야 하는 부분집합 문제이다.

3. 부분집합의 시간 복잡도는 O(2^n)이고, 코어 하나를 택할 때 마다 4방향으로 탐색해야 하기 때문에 시간 복잡도가 더 커진다.
 그러나 3-1. 코어 위를 전선이 지나가지 못하며 3-2. 전선끼리는 교차할 수 없기 때문에 실제로는 모든 방향을 탐색해볼 필요가 없다. 

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

// 210301

public class Solution_D_1767_프로세서연결하기 {
	
	static int N, max, totalCnt, min, map[][];
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static ArrayList<int[]> list; // 고려할 코어만 담는 리스트 (가장자리 코어 배제)
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}

	public static void main(String[] args) throws Exception{
//		System.setIn(new FileInputStream("res/input_D_1767_프로세서연결하기.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = stoi(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			N = stoi(br.readLine());
			map = new int[N][N];
			list = new ArrayList<int[]>();
			max = 0; // 최대로 구할 수 있는 코어 개수
			min = Integer.MAX_VALUE; // 코어 개수가 같다면 전선의 개수가 최소일 때
			totalCnt = 0; // 총 관리해야 할 코어 개수
			
			for(int r=0; r<N; r++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for(int c=0; c<N; c++) {
					map[r][c] = stoi(st.nextToken());
					if(r==0 || c==0 || r==N-1 || c==N-1) continue;
						// 가장자리 무시
					if(map[r][c]==1) {
						list.add(new int[] {r, c});
						++totalCnt;
					}

				}
			}
			go(0, 0);
			System.out.println("#" + tc + " " + min);

		}

		br.close();
	} // main

	static void go(int index, int cCnt) { 	// 선택/비선택 - 부분집합의 논리
		// index : 부분집합에 고려할 코어 인덱스, cCnt : 연결된 코어 개수		
		
		// 남은 코어 수(totalCnt-index) + 현재까지 지나온 코어 수(cCnt) < max 
		// => 앞으로 남은 코어를 다 선택해도 max보다 작음
		// 가지치기
		if(totalCnt-index+cCnt<max) return;
		
		if(index == totalCnt) { // 마지막 코어까지 다 따져봄
			int res = getLength(); // 놓아진 전선의 길이 구하기
			
			if (max<cCnt) {
				max = cCnt; // 코어 개수 갱신
				min = res; // 전선 길이 갱신
			} else if(max==cCnt) {
				if(res<min) min=res;
			}
			return; // 밑에 수행 x
		}
		
		// 코어 선택 전선 놓아보기 (4방향으로 놓아보기)
		int[] cur = list.get(index);
		int r = cur[0]; int c = cur[1]; 
		for(int d=0; d<4; d++) {
			// 현재 위치를 기준으로 끝까지 가보는 시도, 중간에 장애물 만나면 멈춤
			if(isAvailable(r, c, d)) {
				// 전선 놓기
				setStatus(r, c, d, 2); // 2 : 전선놓기
				go(index+1, cCnt+1); // 다음 코어 넘어가기
				// 놓았던 전선 되돌려놓기
				setStatus(r, c, d, 0); // 0 : 원래 상태
				// 어차피 장애물이 없는 위치와 방향에서 2를 놓았기 때문에, 
				// 장애물 검사 없이 0으로 돌려놓기만 하면 됨
			}
		}
		
		// 코어 비선택
		go(index+1,cCnt); 
	}
	
	static void setStatus(int r, int c, int d, int s) { // 상태 s로 놓기
		int nr = r, nc = c;
		while(true) {
			nr += dr[d]; 
			nc += dc[d];
			if(nr<0 || nr>=N || nc<0 || nc>=N) break;
			map[nr][nc] = s;
		}
		
	}
	
	static boolean isAvailable(int r, int c, int d) {
		int nr = r, nc = c;
		while(true) {
			nr += dr[d]; 
			nc += dc[d];
			if(nr<0 || nr>=N || nc<0 || nc>=N) break;
			// 0 빈칸, 1 코어, 2 전선
			if(map[nr][nc]>=1) return false; // 코어나 전선이 놓아져있어 불가능 
		}
		return true;
	}
	
	static int getLength() {
		int lCnt = 0; // 전선이 놓아진 애들은 2
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				if(map[r][c]==2) lCnt++;
			}
		}
		return lCnt;
	}
	
}

 

import java.io.*;
import java.util.*;
// 210317

public class Solution_D_1767_프로세서연결하기_2 {
	static int N, maxCnt, minLen, CN;
	static int[][] map;
	static ArrayList<Pos> coreList;
	static int[] dr = {-1, 0, 0, 1}; // 0  상 1 좌 2 우 3 하
	static int[] dc = {0, -1, 1, 0};
	
	static class Pos {
		int r, c;

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

		@Override
		public String toString() {
			return "Pos [r=" + r + ", c=" + c + "]";
		}
	}
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}
	
	static void subset(int cIdx, int cCnt, int cLen, int L) {
		if(L==CN) {
			// maxCnt, minLen 갱신
			if(maxCnt<cCnt) {
				maxCnt = cCnt;
				minLen = cLen;
			} else if(maxCnt==cCnt) {
				minLen = Math.min(minLen, cLen);
			}
			return;
		}
		
		// cIdx번째 코어 선택
		for(int d=0; d<4; d++) {
			int tmpLen = go(coreList.get(cIdx).r, coreList.get(cIdx).c, d, 0);
			if(tmpLen>0) { // 갈 수 있음
				setStatus(coreList.get(cIdx).r, coreList.get(cIdx).c, d, 2); // 2 전선
				subset(cIdx+1, cCnt+1, cLen+tmpLen, L+1);
				setStatus(coreList.get(cIdx).r, coreList.get(cIdx).c, d, 0); // 0 빈칸 복귀
			}
		}
		// cIdx번째 코어 선택x
		subset(cIdx+1, cCnt, cLen, L+1);
	}
	
	static void setStatus(int r, int c, int d, int status) {
		if(r<0 || r>N || c<0 || c>N) return;
		int nr = r + dr[d]; int nc = c + dc[d];
		if(nr>=0 && nr<N && nc>=0 && nc<N) {
			map[nr][nc] = status;
			setStatus(nr, nc, d, status);
		}
	}
	
	static int go(int r, int c, int d, int len) {
		if(r==0 || r==(N-1) || c==0 || c==(N-1)) return len;
		
		int nr = r + dr[d]; int nc = c + dc[d];
		if(map[nr][nc]==0) {
			return go(nr, nc, d, len+1);
		}
		else return 0;
	}
	
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		
		int T = stoi(br.readLine().trim());
		
		for(int tc=1; tc<=T; tc++) {
			N = stoi(br.readLine().trim());
			maxCnt = 0; minLen = Integer.MAX_VALUE;
			map = new int[N][N];
			CN = 0;
			coreList = new ArrayList<>();
				
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine().trim(), " ");
				for(int j=0; j<N; j++) {
					map[i][j] = stoi(st.nextToken());
					if(map[i][j]==1) { //  코어
						if(i==0 || i==(N-1) || j==0 || j==(N-1)) continue;
						coreList.add(new Pos(i, j));
						++CN;		
					}
				}
			} // input
			subset(0, 0, 0, 0);
			sb.append("#" + tc + " " + minLen+"\n");

		} // tc
		
		System.out.println(sb.toString());
		br.close();
	}