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

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf&categoryId=AV4suNtaXFEDFAUf&categoryType=CODE

괜히 뭔가 최적화한다고 로직을 복잡하게 짜는거 보다, 완전 탐색으로 깔끔하게 짜는게 더 나았던 케이스.
– 우선 맵 정보를 저장
– 이미 edge에 있는 CPU들은 전선 길이 0으로 연결되어 있다고 가정하고 있으므로, 계산에서 제외
– 나머지 edge에 있지 않은 CPU들은 추가하는 경우 (좌/우/상/하)와 추가하지 않는 경우까지 5가지 경우가 있음 (즉 O(5n)의 복잡도)
– Edge에 있지 않은 CPU들을 대상으로, DFS로 recursive하게 (즉 재귀적으로) brute-force search (완전 탐색)을 수행함
(매 단계 추가하는 경우는 갱신된 정보를, 추가하지 않는 경우 갱신되지 않은 정보를 다음 단계로 넘김)
– 매 단계 CPU가 추가될 수 없는 경우라도, 추가하지 않는 경우로 간주하고 계속 다음 단계로 넘어가기 때문에, 최종적인 update는 마지막 단계에서 수행
– 마지막 단계에서 상하좌우로 추가하는 경우와  추가하지 않는 경우까지 감안해서 CPU 수가 최대로 되면서 전선 길이가 최소로 되는 경우를 계속 global하게 업데이트함

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

public class Solution {	
	public static int maxCPU = 0;		// Global한 최대 CPU 값 
	public static int minValue = 1000;	// Global한 최소 전선 길이
	public static ArrayList<Vertex> myList = null;	// 처리해야 될 CPU 목록 (파라미터로 넘기기 번거로워서)
	
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int i = 0; i < numCases; i++) {				
				writer.write("#" + String.valueOf(i + 1) + " ");
				
				int numN = Integer.parseInt(reader.readLine());	// 맵 가로/세로 폭
			
				maxCPU = 0;			// 매번 초기화 
				minValue = 1000;	// 매번 초기화
				myList = new ArrayList<Vertex>(); // 매번 초기화
				
				// map 작성
				int[][] mapArray = new int[numN][numN];
				for (int j = 0; j < numN; j++) {	// j가 세로라는 것을 유의해야 함
					StringTokenizer tmp = new StringTokenizer(reader.readLine(), " ");
					int idx = 0;
					while (tmp.hasMoreTokens()) {
						int tmp_ = Integer.parseInt(tmp.nextToken());
						if (tmp_ != 0) {
							mapArray[idx][j] = tmp_;
							
							// edge에 있는 요소들은 따로 계산할 필요가 없음 (j-세로 나 idx-가로가 edge에 걸쳐져 있으면 추가하지 않음)
							if (!(j == 0 || j == numN - 1 || idx == 0 || idx == numN - 1))
								myList.add(new Vertex(idx, j));
						}
						
						idx++;
					}
				}

				// 실제로 CPU를 최대한 넣으면서, 길이가 최소인 경우를 탐색 
				// depth=0, currentNumCPU=0, currentLength=0
				search(0, mapArray, 0, 0);

				writer.write(minValue + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	// 실제로 CPU를 최대한 넣으면서, 길이가 최소인 경우를 탐색 
	// (currentDepth: 몇 번째 vertex를 처리해야 하는가, map: 현재까지의 지도 처리 정보, currentNumCPU: 현재까지 포함된 CPU의 수, currentLength: 현재까지의 전선 길이)
	public static void search(int currentDepth, int[][] map, int currentNumCPU, int currentLength) {
		// 현재 처리해야 될 CPU 정보 획득
		Vertex v = myList.get(currentDepth);

		// 만약 최대 깊이까지 왔다면 
		if (currentDepth == myList.size() - 1) {
			int maxCPU_ = 0;		// Local한 최대 CPU 갯수
			int minValue_ = 1000;	// Local한 최소 전선 길이 
			
			int retVal = 0;
			// 위로 전선을 연결할 수 있는 경우
			if ((retVal = safeToAdd(map, v.X, v.Y, "U")) > 0) {
				maxCPU_ = currentNumCPU + 1;
				// 필요한 경우 최소값 갱신
				if (minValue_ > currentLength + retVal)
					minValue_ = currentLength + retVal;
			}
			// 아래로 전선을 연결할 수 있는 경우
			if ((retVal = safeToAdd(map, v.X, v.Y, "D")) > 0) {
				maxCPU_ = currentNumCPU + 1;
				// 필요한 경우 최소값 갱신
				if (minValue_ > currentLength + retVal)
					minValue_ = currentLength + retVal;
			}
			// 왼쪽으로 전선을 연결할 수 있는 경우
			if ((retVal = safeToAdd(map, v.X, v.Y, "L")) > 0) {
				maxCPU_ = currentNumCPU + 1;
				// 필요한 경우 최소값 갱신
				if (minValue_ > currentLength + retVal)
					minValue_ = currentLength + retVal;
			}
			// 오른쪽으로 전선을 연결할 수 있는 경우
			if ((retVal = safeToAdd(map, v.X, v.Y, "R")) > 0) {
				maxCPU_ = currentNumCPU + 1;
				// 필요한 경우 최소값 갱신
				if (minValue_ > currentLength + retVal)
					minValue_ = currentLength + retVal;
			}
			// 전선이 연결될 수 없는 경우 (minValue_가 계속 1000)
			if (minValue_ == 1000) {
				maxCPU_ = currentNumCPU;	// 이전 정보 그대로
				minValue_ = currentLength; 	// 이전 정보 그대로
			}
			
			// Global값보다 더 큰 경우 갱신 
			if (maxCPU_ > maxCPU) {
				maxCPU = maxCPU_;
				minValue = minValue_;
			}
			// Global 값과 같지만 전선 길이가 더 짧은 경우 갱신 
			else if (maxCPU_ == maxCPU) {
				if (minValue > minValue_)
					minValue = minValue_;
			}
			
			return;
		}

		// 이외의 기본 경우 
		int retVal = 0;
		// 위로 갈 수 있는 경우. 위로 전선 연결한 정보 (Map, CPU 갯수, 전선 길이) 갱신 후 다음 단계로 넘어감 
		if ((retVal = safeToAdd(map, v.X, v.Y, "U")) > 0)
			search(currentDepth + 1, addToMap(map, v.X, v.Y, "U"), currentNumCPU + 1, currentLength + retVal);
		// 아래로 갈 수 있는 경우. 아래로 전선 연결한 정보 (Map, CPU 갯수, 전선 길이) 갱신 후 다음 단계로 넘어감 
		if ((retVal = safeToAdd(map, v.X, v.Y, "D")) > 0)
			search(currentDepth + 1, addToMap(map, v.X, v.Y, "D"), currentNumCPU + 1, currentLength + retVal);
		// 왼쪽으로 갈 수 있는 경우. 왼쪽으로 전선 연결한 정보 (Map, CPU 갯수, 전선 길이) 갱신 후 다음 단계로 넘어감 
		if ((retVal = safeToAdd(map, v.X, v.Y, "L")) > 0)
			search(currentDepth + 1, addToMap(map, v.X, v.Y, "L"), currentNumCPU + 1, currentLength + retVal);
		// 오른쪽으로 갈 수 있는 경우. 오른쪽으로 전선 연결한 정보 (Map, CPU 갯수, 전선 길이) 갱신 후 다음 단계로 넘어감 
		if ((retVal = safeToAdd(map, v.X, v.Y, "R")) > 0)
			search(currentDepth + 1, addToMap(map, v.X, v.Y, "R"), currentNumCPU + 1, currentLength + retVal);
		// 현재 CPU를 추가 안하는 경우. 정보 갱신 없이 다음 단계로 넘어감 
		search(currentDepth + 1, map, currentNumCPU, currentLength);
	}
	
	// 추가 가능한 경우 추가된 전선 길이를 (>0), 불가능한 경우 -1을 리턴함
	// (map: 현재 지도, x: 추가할 CPU의 x 좌표, y: 추가할 CPU의 y 좌표, direction: 전선의 방향)
	public static int safeToAdd(int[][] map, int x, int y, String direction) {
		int isSafe = 0;
		
		switch (direction) {
		// 위로 추가하는 경우 
		case "U":
			for (int i = y - 1; i >= 0; i--) {
				if (map[x][i] != 0) {
					isSafe = -1;
					break;
				}
				else
					isSafe++;
			}
			break;
		// 아래로 추가하는 경우 
		case "D":
			int tmp_ = map[x].length;
			for (int i = y + 1; i < tmp_; i++) {
				if (map[x][i] != 0) {
					isSafe = -1;
					break;
				}
				else
					isSafe++;
			}
			break;
		// 왼쪽으로 추가하는 경우 
		case "L":
			for (int i = x - 1; i >= 0; i--) {
				if (map[i][y] != 0) {
					isSafe = -1;
					break;
				}
				else
					isSafe++;
			}
			break;
		// 오른쪽으로 추가하는 경우 
		case "R":
			int tmp2_ = map.length;
			for (int i = x + 1; i < tmp2_; i++) {
				if (map[i][y] != 0) {
					isSafe = -1;
					break;
				}
				else
					isSafe++;
			}
			break;
		}
		
		return isSafe;
	}
	// 실제 지도에 추가 (addToMap 자체는 검증 기능이 없으므로 safeToAdd 함수로 확인 먼저 할 필요 있음)
	// (map: 현재 지도, x: 추가할 CPU의 x 좌표, y: 추가할 CPU의 y 좌표, direction: 전선의 방향)
	// (리턴값: 갱신된 지도)
	public static int[][] addToMap(int[][] map, int x, int y, String direction) {
		// 2차원 배열 복사
		int[][] map_ = new int[map.length][map.length];
		
		for(int i=0; i<map.length; i++)
			for(int j=0; j<map[i].length; j++)
				map_[i][j]=map[i][j];
		
		// CPU 있는 곳은 1로 마킹되어 있음. 전선은 2로 마킹함
		switch (direction) {
		case "L": // 2
			for (int i = x - 1; i >= 0; i--) {
				map_[i][y] = 2;
			}
			break;
		case "R": // 2
			int tmp2_ = map.length;
			for (int i = x + 1; i < tmp2_; i++) {
				map_[i][y] = 2;
			}
			break;
		case "U": // 2
			for (int i = y - 1; i >= 0; i--) {
				map_[x][i] = 2;
			}
			break;
		case "D": // 2
			int tmp_ = map[x].length;
			for (int i = y + 1; i < tmp_; i++) {
				map_[x][i] = 2;
			}
			break;
		}
		
		return map_;
	}
}

// CPU 정보 (x, y 좌표)
class Vertex {
	public int X;
	public int Y;
	
	public Vertex(int X_, int Y_) {
		this.X = X_;
		this.Y = Y_;
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.