(Java) 2112. [모의 SW 역량테스트] 보호 필름

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

왜 정답률이 낮은지 깨달은 문제.
– 뭔가 다른 방식의 완전 탐색으로 푸니까 시간 초과가 떠서 머리를 다시 굴림.
– 결국 각 막마다 A를 칠할 것이냐, B를 칠할 것이냐, 칠하지 않을 것이냐 해서 DFS로 모든 경우의 수를 탐색하는 문제였음.
– 각 막의 약품 처리 여부에 따라 지도가 계속 정보가 바뀌는데, 지도 전체를 계속 복사해서 쓰면 시간 소요가 크기 때문에, 수정하는 부분 (한 줄)만 백업해두고 값 바꾼 후 다시 값 복원하는 식으로 시간 효율을 올림.
– 어째저째 겨우겨우 통과함. 완전 탐색으로 짤 때, 쉽게 생각해야 가짓수를 쓸데없이 늘리는 실수를 안 함.

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

public class Solution {
	public static int minLevel = 1000;	// 최소값 찾는 것이기 때문에 최대 가능한 값보다 큰 값으로
	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));

		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) + " ");

				// 최소값 찾는 것이기 때문에 최대한 큰 값으로
				minLevel = 1000;

				// height: 두께 (Y), width: 가로크기 (X), threshold: 합격기준 
				String[] tmp = reader.readLine().split(" ");

				int height = Integer.parseInt(tmp[0]);
				int width = Integer.parseInt(tmp[1]);
				int threshold = Integer.parseInt(tmp[2]);

				// map 제작
				int[][] map = new int[height][width];
				for (int j = 0; j < height; j++) {
					String[] tmp_ = reader.readLine().split(" ");
					for (int k = 0; k < tmp_.length; k++) {
						map[j][k] = Integer.parseInt(tmp_[k]);
					}
				}
		
				// 한 번에 통과하는지 체크 
				if (checkPass(map, threshold) == true) {
					writer.write("0" + System.lineSeparator());
					continue;
				}
				// 안 되는 경우, 쭉 체크
				process(0, map, 0, threshold);

				writer.write(minLevel + System.lineSeparator());
				writer.flush();
			}			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}	
	
	public static void process(int depth, int[][] map, int numTry, int threshold) {
		// 마지막 depth까지 안 되서 온 경우, 각 경우 처리 
		if (depth == map.length - 1) {
			// 안 고치고 가능한지 시도 (가장 적은 numTry 경우)
			if (checkPass(map, threshold) == true) {
				if (minLevel > numTry)
					minLevel = numTry;
				return;
			}
			
			// A 칠하고 나서 통과 여부 검사 
			// 지도 복구하기 위한 정보들 
			int[] toRestore = new int[map[depth].length];
			for(int i = 0; i < map[depth].length; i++)
				toRestore[i] = map[depth][i];
			Arrays.fill(map[depth], 0); // 0: A

			// A 칠해서 통과하면, 더 진행할 필요가 없음
			if (checkPass(map, threshold) == true) {
				if (minLevel > numTry + 1)
					minLevel = numTry + 1;
				
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	

				return;
			}
			else {
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	
			}
			
			// B 칠하고 나서 통과 여부 검사
			// 지도 복구하기 위한 정보들 
			toRestore = new int[map[depth].length];
			for(int i = 0; i < map[depth].length; i++)
				toRestore[i] = map[depth][i];
			Arrays.fill(map[depth], 1); // 1: B

			// B 칠해서 통과하면, 더 진행할 필요가 없음
			if (checkPass(map, threshold) == true) {
				if (minLevel > numTry + 1)
					minLevel = numTry + 1;
				
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	
			}
			else {
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	
			}
			
			return;	
		}
		
		// Case 1: A (A 칠하고 통과 여부 검사)
		int[] toRestore = new int[map[depth].length];
		for(int i = 0; i < map[depth].length; i++)
			toRestore[i] = map[depth][i];
		Arrays.fill(map[depth], 0);

		// A 칠해서 통과하면, 더 진행할 필요가 없음
		if (checkPass(map, threshold) == true) {
			if (minLevel > numTry + 1)
				minLevel = numTry + 1;
			
			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];	

			return;
		}
		else {
			// A를 칠한 경우이므로 numTry 1 증가
			process(depth + 1, map, numTry + 1, threshold);			
		
			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];
		}
		
		// Case 2: B (B 칠하고 통과 여부 검사)
		toRestore = new int[map[depth].length];
		for(int i = 0; i < map[depth].length; i++)
			toRestore[i] = map[depth][i];
		Arrays.fill(map[depth], 1);
		
		//B 칠해서 통과하면, 더 진행할 필요가 없음
		if (checkPass(map, threshold) == true) {
			if (minLevel > numTry + 1)
				minLevel = numTry + 1;

			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];	
			
			return;
		}
		else {
			// B를 칠한 경우이므로 numTry 1 증가
			process(depth + 1, map, numTry + 1, threshold);	

			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];	
		}

		// Case 3: X (약품 처리 안하고 통과 여부 검사)
		if (checkPass(map, threshold) == true) {
			if (minLevel > numTry)
				minLevel = numTry;
			return;
		}
		else {
			// 약품 처리 안 했으므로, numTry는 그대로
			process(depth + 1, map, numTry, threshold);
		}
	}
	
	public static boolean checkPass(int[][] map, int threshold) {
		boolean passed = true;
		
		// 시험 통과 여부 판별
		for (int i = 0; i < map[0].length; i++) {
			int currentIdx = map[0][i];
			int count = 1;

			for (int j = 1; j < map.length; j++) {
				if (currentIdx == map[j][i]) {
					count++;
					
					// 이미 합격한 경우 더 이상 진행하지 않음
					if (count == threshold)
						break;
				}
				else { // 달라진 경우 
					currentIdx = map[j][i];
					count = 1;
				}
			}
			
			// threshold를 넘긴 경우가 없을 경우, 실패로 처리하고 return
			if (count < threshold) {
				passed = false;
				break;
			}
		}
		
		return passed;
	}
}

(Java) 2105. [모의 SW 역량테스트] 디저트 카페

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

마찬가지로 완전 탐색 문제.
– 대각선으로 간다고 해서 복잡하게 생각하지 말고, 경우를 나누면 됨
(예를 들어 4X4에서 대각선으로 갈 수 있는 경우는 3X3 사각형에서 위쪽 가운데에서 마름모 모양으로 내려오는 경우 1개, 4X4 사각형에서 오른쪽 대각 방향 사각형, 왼쪽 대각 방향 사각형 2개 해서 총 3가지 종류이다.)
– 이를 일반화하면 다음과 같다.
3X3 사각형에서 (1,0)에서 좌-하-우-상으로 순회하는 사각형 1개 (총 1개)
4X4 사각형에서 (1,0)에서 좌-하-우-상으로 순회하는 사각형 1개, (2,0)에서 좌-하-우-상으로 순회하는 사각형 1개 (총 2개)
5X5 사각형에서 (1,0)에서 좌-하-우-상으로 순회하는 사각형 1개, (2,0)에서 좌-하-우-상으로 순회하는 사각형 1개, (3,0)에서 좌-하-우-상으로 순회하는 사각형 1개 (총 3개)
….
– 이를 활용해서 실제 지도에서 값을 구할 때는 (N이 5라고 가정)
5X5 맵에서 3X3 사각형을 총 9개 (솔루션 1개*가능한 위치 9개), 4X4 사각형을 총 8개 (솔루션 2개*가능한 위치 4개), 5X5 사각형을 총 3개 (솔루션 3개*가능한 위치 1개) 해서 총 20번 탐색하면 된다.
이 중 사각형이 끝까지 이어진 경우만 모아서 종류의 최대값을 구하면 문제에서 원하는 답이 나옴.
– 최적화를 위해, 테스트 케이스 이어질 때 이미 구한 사각형 종류는 중복해서 구하지 않도록 함 (너무 꼼수 같아서 뺐음)

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

public class Solution {
	// 크기 별 가능한 순회 모양 세트
	public static TreeMap<Integer, List<List<String>>> solutionCases = new TreeMap<Integer, List<List<String>>>();
	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));

		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());
				int maxValue = -1;	// 갱신된 적이 없는 경우 (=가능한 경우 없음) -1 출력
				
				// Map 생성
				int[][] map = new int[numN][numN];
				for (int j = 0; j < numN; j++) {
					String[] tmp = reader.readLine().split(" ");
					
					for (int k = 0; k < numN; k++) {
						map[k][j] = Integer.parseInt(tmp[k]);
					}
				}
				
				solutionCases.clear();

				// 3*3부터 N*N까지 순회 가능한 케이스 모두 작성
				for (int j = 3; j <= numN; j++) {
					solutionCases.put(j, new ArrayList<List<String>>());
					
					// 상단 edge에서 왼쪽 edge -> 하단 edge -> 오른쪽 edge -> 상단 edge로 돌아온다고 가정했을 때,
					// 출발 가능한 곳은 (1,0)부터 (j-2,0)까지임 (즉, 두번째부터 끝에서 두번째까지)
					List<String> startPoints = new LinkedList<String>();
					for (int k = 1; k <= j - 2; k++)
						startPoints.add(k + "/0");
					
					// 시작점 별로 사각형을 그림
					for(String startPoint: startPoints) {
						String[] tmp = startPoint.split("/");
						int x = Integer.parseInt(tmp[0]);
						int y = Integer.parseInt(tmp[1]);
						
						List<String> pathInfo = new ArrayList<String>();
						
						// 1단계: 왼쪽 edge로 (x--, y++)
						while (x > 0) {
							pathInfo.add("-1/1");
							
							x--;
							y++;
						}
						
						// 2단계: 하단 edge로 (x++, y++)
						while (y < j - 1) {
							pathInfo.add("1/1");
							
							x++;
							y++;
						}
						
						// 3단계: 오른쪽 edge로 (x++, y--)
						while (x < j - 1) { pathInfo.add("1/-1"); x++; y--; } // 4단계: 상단 edge로 (x--, y--) while (y > 0) {
							pathInfo.add("-1/-1");
							
							x--;
							y--;
						}
						
						solutionCases.get(j).add(pathInfo);
					}
				}
			
				// 맵에 따라 실제로 탐방 
				// (numN=4이면 3*3은 시작점이 (1,0), (1,1), (2,0), (2,1)이고
				// 4*4는 처음 사각형은 시작점은 (1,0), 두번째 사각형은 시작점이 (2,0)) 
				for (int j = 3; j <= numN; j++) {
					List<List<String>> solutionCase = solutionCases.get(j);
					
					int tmp_ = solutionCase.size();
					
					// J*J의 각 솔루션(=각 사각형) 별로 실제 맵에 매핑될 수 있는 위치들을 구함  
					for (int k = 0; k < tmp_; k++) {
						int startX = k + 1;	// 시작점 (X)
						int startY = 0;		// 시작점 (Y)
						
						// 시작점 기준 실제 맵에서 가능한 경우의 수 모두 탐색
						List<String> offsetList = new ArrayList<String>();
						for (int l = 0; l <= numN - j; l++) {
							for (int m = 0; m <= numN - j; m++) {
								offsetList.add(l + "/" + m);
							}
						}
						
						// 모든 가능한 경우 별로 디저트 수 카운트
						for (String offset: offsetList) {
							String[] tmp__ = offset.split("/");
							int offsetX = Integer.parseInt(tmp__[0]);
							int offsetY = Integer.parseInt(tmp__[1]);

							// 디저트 목록을 넣을 리스트
							List<Integer> dessertList = new ArrayList<Integer>();

							// 사각형의 점 갯수
							int tmp___ = solutionCase.get(k).size();
							
							// 실제 맵 내에서의 시작점 (X, Y)
							int X = startX + offsetX;
							int Y = startY + offsetY;
							
							// solutionCase를 순회하면서, dessert 값 더함
							for (int l = 0; l < tmp___; l++) { int dessertValue = map[X][Y]; // 아직 없는 디저트라면 OK if (dessertList.contains(dessertValue) == false) { dessertList.add(dessertValue); // 다음 이동 방향대로 X, Y를 이동 String[] nextDirection = solutionCase.get(k).get(l).split("/"); X += Integer.parseInt(nextDirection[0]); Y += Integer.parseInt(nextDirection[1]); } else // 이미 있는 디저트면 루프를 더 돌지 않음 break; } // 순회를 다 못한 경우는 제외 if (dessertList.size() != solutionCase.get(k).size()) continue; // 순회를 다한 경우, 최대값 갱신 if (dessertList.size() > maxValue)
								maxValue = dessertList.size();
						}
					}
				}
				
				writer.write(maxValue + System.lineSeparator());
				writer.flush();
			}			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

(Java) 1953. [모의 SW 역량테스트] 탈주범 검거

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

어려운 문제는 아니지만, 그래도 고려할 사항들이 있는 문제들.
– 맵 형성 자체는 뭐 반복되는 거니까 설명 생략함.
– 다만 맵의 모든 곳에 파이프가 있는 것이 아니기 때문에, visited 체크 겸용으로 simpleMap 변수를 이용 (1은 파이프가 있음, 2는 방문한 곳)
– 기본적으로는 DFS로 depth를 하나씩 키워가면서 탐색하는 방식. 이미 탐색한 곳은 중복으로 후보에 넣지 않고 넓혀 나감.
– 함정 하나가, 현재 위치의 파이프 모양을 보고 방향을 결정지어도 갈 방향의 파이프가 맞지 않으면 갈 수 없는 방향임. 이를 감안해서 후보지 알고리즘을 작성함.
– 시간이 안 됐지만 더 이상 후보지가 없다면 미리 빠져나와서 시간 절약.

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

public class Solution {		
	public static int[][] map = null;
	public static int[][] simpleMap = null;
	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));

		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) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				int height = Integer.parseInt(tmp[0]);		// 세로 크기 (Y)
				int width = Integer.parseInt(tmp[1]);		// 가로 크기 (X)
				int manholeX = Integer.parseInt(tmp[3]);	// 맨홀 X
				int manholeY = Integer.parseInt(tmp[2]);	// 맨홀 Y
				int timeCons = Integer.parseInt(tmp[4]);	// 소요한 시간

				// Map 만들기
				map = new int[width][height];
				// simpleMap은 visited 겸용으로 쓰임 (1: 파이프가 있음, 2: 방문함)
				simpleMap = new int[width][height]; 
				
				for (int j = 0; j < height; j++) {
					int idx = 0;

					StringTokenizer st = new StringTokenizer(reader.readLine(), " ");
					while (st.hasMoreTokens()) {
						int tmp_ = Integer.parseInt(st.nextToken());
						if (tmp_ != 0) {
							map[idx][j] = tmp_;
							simpleMap[idx][j] = 1;
						}
						
						idx++;
					}
				}
				
				int maxApproach = 0;
				// 가야할 후보지 
				Queue<Vertex> myQueue = new LinkedList<Vertex>();
				// 이미 간 곳 stack에 넣음 (사실 count로 해도 됨)
				Stack<Vertex> myStack = new Stack<Vertex>();
				
				// 맨홀에서 시작
				myQueue.add(new Vertex(manholeX, manholeY));
				
				// 갈 수 있는 후보를 모두 탐색
				for (int j = 1; j <= timeCons; j++) {
					// 1000, 1000은 탈출 조건을 위함 (일종의 구분자 역할)
					myQueue.add(new Vertex(1000, 1000));
					
					Vertex v = myQueue.poll();
					while ((v.X == 1000 && v.Y == 1000) == false) {
						// 현재 vertex: v
						if (simpleMap[v.X][v.Y] == 1) { // 중복 방문 허용 안함
							simpleMap[v.X][v.Y] = 2;
							myStack.add(v);
							
							List<Vertex> cand = findCandidate(v.X, v.Y);
							// 아직 방문하지 않은 다음 공간이 있는 경우
							if (cand != null) {
								// 해당 후보 vertex 추가
								for (Vertex vv: cand) {
									myQueue.add(vv);
								}
							}
						}
						
						v = myQueue.poll();
					}
					
					// 더 이상 갈 수 있는 공간이 없으면 탈출
					if (myQueue.size() == 0)
						break;
				}
				
				maxApproach = myStack.size();
				writer.write(maxApproach + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public static List<Vertex> findCandidate(int x, int y) {
		List<Vertex> cand = new LinkedList<Vertex>();
		
		boolean toLeft = false;
		boolean toRight = false;
		boolean toUp = false;
		boolean toDown = false;
		
		// 현재 위치가 어디로 갈 수 있는지 확인 (왼쪽)
		switch (map[x][y]) {
		case 1: case 3: case 6: case 7:
			int leftBound = 0;
			// 왼쪽에 공간이 있고, 파이프가 있고 방문하지 않은 곳
			if (x - 1 >= leftBound && simpleMap[x - 1][y] == 1)
				toLeft = true;
		}
		
		// 현재 위치가 어디로 갈 수 있는지 확인 (오른쪽)
		switch (map[x][y]) {
		case 1: case 3: case 4: case 5:
			int rightBound = map.length - 1;
			// 오른쪽에 공간이 있고, 파이프가 있고 방문하지 않은 곳
			if (x + 1 <= rightBound && simpleMap[x + 1][y] == 1)
				toRight = true;
		}

		// 현재 위치가 어디로 갈 수 있는지 확인 (위)
		switch (map[x][y]) {
		case 1: case 2: case 4: case 7:
			int upBound = 0;
			// 위에 공간이 있고, 파이프가 있고 방문하지 않은 곳
			if (y - 1 >= upBound && simpleMap[x][y - 1] == 1)
				toUp = true;
		}

		// 현재 위치가 어디로 갈 수 있는지 확인 (아래)
		switch (map[x][y]) {
		case 1: case 2: case 5: case 6:
			int downBound = map[x].length - 1;
			// 아래에 공간이 있고, 파이프가 있고 방문하지 않은 곳
			if (y + 1 <= downBound && simpleMap[x][y + 1] == 1)
				toDown = true;
		}

		if (toLeft == true) {
			switch (map[x - 1][y]) {
			// 왼쪽에 있는 파이프가 오른쪽을 향한 경우에만 접근 가능
			case 1: case 3: case 4: case 5:
				cand.add(new Vertex(x - 1, y));
			}
		}
		if (toRight == true) {
			switch (map[x + 1][y]) {
			// 오른쪽에 있는 파이프가 왼쪽을 향한 경우에만 접근 가능
			case 1: case 3: case 6: case 7:
				cand.add(new Vertex(x + 1, y));
			}
		}
		if (toUp == true) {
			switch (map[x][y - 1]) {
			// 위에 있는 파이프가 아래를 향한 경우에만 접근 가능
			case 1: case 2: case 5: case 6:
				cand.add(new Vertex(x, y - 1));
			}
		}
		if (toDown == true) {
			switch (map[x][y + 1]) {
			// 아래에 있는 파이프가 위를 향한 경우에만 접근 가능
			case 1: case 2: case 4: case 7:
				cand.add(new Vertex(x, y + 1));
			}
		}
		
		return cand;
	}
}

class Vertex {
	public int X;
	public int Y;
	
	public Vertex(int X_, int Y_) {
		this.X = X_;
		this.Y = Y_;
	}
}

(JAVA) 1949. [모의 SW 역량테스트] 등산로 조성

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

이 문제도 마찬가지로, 어설픈 최적화는 시간만 잡아 먹음. 분명하게 설명할 수 있는 이유가 있을 때만 최적화를 하는게 살 길이다.
– 우선 맵 정보를 저장 (최대값이 담긴 vertex들은 따로 저장)
– 이 문제도 DFS로 완전 탐색을 수행.
– 각 최고점마다 총 4가지+4가지 경우를 탐색해야 함. (기본적인 좌우상하 4가지 + 기본 좌우상하 중 안 될 때 공사해서 갈 수 있는 경우 최대 4가지)
(공사 없이 좌 > 좌가 안 될 경우 공사해서 좌로 갈 수 있으면 공사 후 좌 /
공사 없이 우 > 우가 안 될 경우 공사해서 우로 갈 수 있으면 공사 후 우 /
공사 없이 상 > 상이 안 될 경우 공사해서 상으로 갈 수 있으면 공사 후 상 /
공사 없이 하 > 하가 안 될 경우 공사해서 하로 갈 수 있으면 공사 후 하)
– 위의 8가지 경우는 다음으로 진행할 때 경로 길이를 +1해서 진행
(단, 8가지 중 한 가지도 해당 안되는 경우 최종으로 보고 경로 길이 +1해서 global max length를 계산)
– 모든 경우를 탐색한 후, 최대 길이의 경로를 출력함

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

public class Solution {		
	public static int numN = 0;	// 맵 크기 (가로, 세로)
	public static int numK = 0;	// 공사 허용 한계 
	public static int maxLength = 0; // Global한 최대 길이

	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));

		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) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				numN = Integer.parseInt(tmp[0]);	// 맵 크기 (가로, 세로)
				numK = Integer.parseInt(tmp[1]);	// 공사 허용 한계 
				
				// 최대 높이 
				List<Vertex> maximumHeightList = new LinkedList<Vertex>();
				int maxHeight = 0;
				maxLength = 0;		// 적절한 초기화
				
				// map 작성
				int[][] mapArray = new int[numN][numN];
				for (int j = 0; j < numN; j++) { // 세로줄
					StringTokenizer tmp_ = new StringTokenizer(reader.readLine(), " ");
					int idx = 0; // 가로줄
					
					while (tmp_.hasMoreTokens()) {
						int tmp__ = Integer.parseInt(tmp_.nextToken());
						mapArray[idx][j] = tmp__;							
						
						// 최대값이 새로 나온 경우 기존 리스트 클리어
						if (tmp__ > maxHeight) {
							maxHeight = tmp__;
							maximumHeightList.clear();
						}

						// 새로운 최대값에 맞는 것만 삽입
						if (tmp__ == maxHeight)
							maximumHeightList.add(new Vertex(idx, j));
						
						idx++;
					}
				}
				
				for(Vertex v: maximumHeightList) {
					boolean[][] visited = new boolean[numN][numN];

					findPath(mapArray, visited, v.X, v.Y, 0, false);
				}
				
				writer.write(maxLength + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	// 실제 경로 탐색 
	// map: 지도, visited: 방문 정보, x: 현재 있는 곳 x 좌표, y: 현재 있는 곳 y 좌표, currentLength: 현재 길이, constructed: 공사 유무
	public static void findPath(int[][] map, boolean[][] visited, int x, int y, int currentLength, boolean constructed) {
		Vertex v = null;
		
		// 왼쪽
		v = findCandidate(map, visited, x, y, "L");
		if (v != null) {
			visited[x][y] = true;
			findPath(map, visited, v.X, v.Y, currentLength + 1, constructed);
			visited[x][y] = false; // 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
		}
		// 공사한 경우 포함 (단, 공사 없이도 이미 갈 수 있는 곳은 공사하지 않음. 오히려 length가 줄어들 수 있음) 
		if (v == null && constructed == false) {
			int[][] newMap = findConstructedMap(map, visited, x, y, "L", numK);
			if (newMap != null) {
				v = findCandidate(newMap, visited, x, y, "L");

				constructed = true;		// 공사가 된 경우에만 true로 
				visited[x][y] = true;	// 공사가 된 경우에만 true로 
				findPath(newMap, visited, v.X, v.Y, currentLength + 1, constructed);
				visited[x][y] = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
				constructed = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
			}
		}
		
		// 오른쪽
		v = findCandidate(map, visited, x, y, "R");
		if (v != null) {
			visited[x][y] = true;
			findPath(map, visited, v.X, v.Y, currentLength + 1, constructed);
			visited[x][y] = false; // 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
		}
		// 공사한 경우 포함 (단, 공사 없이도 이미 갈 수 있는 곳은 공사하지 않음. 오히려 length가 줄어들 수 있음) 
		if (v == null && constructed == false) {
			int[][] newMap = findConstructedMap(map, visited, x, y, "R", numK);
			if (newMap != null) {
				v = findCandidate(newMap, visited, x, y, "R");

				constructed = true;		// 공사가 된 경우에만 true로 
				visited[x][y] = true;	// 공사가 된 경우에만 true로 
				findPath(newMap, visited, v.X, v.Y, currentLength + 1, constructed);
				visited[x][y] = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
				constructed = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
			}
		}
		
		// 위
		v = findCandidate(map, visited, x, y, "U");
		if (v != null) {
			visited[x][y] = true;
			findPath(map, visited, v.X, v.Y, currentLength + 1, constructed);
			visited[x][y] = false; // 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
		}
		// 공사한 경우 포함 (단, 공사 없이도 이미 갈 수 있는 곳은 공사하지 않음. 오히려 length가 줄어들 수 있음) 
		if (v == null && constructed == false) {
			int[][] newMap = findConstructedMap(map, visited, x, y, "U", numK);
			if (newMap != null) {				
				v = findCandidate(newMap, visited, x, y, "U");

				constructed = true;		// 공사가 된 경우에만 true로 
				visited[x][y] = true;	// 공사가 된 경우에만 true로 
				findPath(newMap, visited, v.X, v.Y, currentLength + 1, constructed);
				visited[x][y] = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
				constructed = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
			}
		}
		
		// 아래
		v = findCandidate(map, visited, x, y, "D");
		if (v != null) {
			visited[x][y] = true;
			findPath(map, visited, v.X, v.Y, currentLength + 1, constructed);
			visited[x][y] = false; // 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
		}
		// 공사한 경우 포함 (단, 공사 없이도 이미 갈 수 있는 곳은 공사하지 않음. 오히려 length가 줄어들 수 있음) 
		if (v == null && constructed == false) {
			int[][] newMap = findConstructedMap(map, visited, x, y, "D", numK);
			if (newMap != null) {				
				v = findCandidate(newMap, visited, x, y, "D");
				
				constructed = true;		// 공사가 된 경우에만 true로 
				visited[x][y] = true;	// 공사가 된 경우에만 true로 
				findPath(newMap, visited, v.X, v.Y, currentLength + 1, constructed);
				visited[x][y] = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
				constructed = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
			}
		}
		
		// 더 이상 갈 곳이 없으면
		if (v == null) {
			// 그 전 vertex가 포함되었을 때 기준이므로, 이번 vertex가 마지막이면 그것도 포함해야 됨
			if (currentLength + 1 > maxLength)
				maxLength = currentLength + 1;
		}
	}
	
	// 주어진 방향으로 다음 후보를 탐색 
	public static Vertex findCandidate(int[][] map, boolean[][] visited, int x, int y, String direction) {
		int leftBound = 0;
		int rightBound = map[0].length - 1;
		int upBound = 0;
		int downBound = map.length - 1;
		
		// 왼쪽
		if (direction.equals("L") && x - 1 >= leftBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x - 1][y] != true && map[x][y] > map[x - 1][y])
				return new Vertex(x - 1, y);
		}
		
		// 오른쪽
		if (direction.equals("R") && x + 1 <= rightBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x + 1][y] != true && map[x][y] > map[x + 1][y])
				return new Vertex(x + 1, y);			
		}
		
		// 위
		if (direction.equals("U") && y - 1 >= upBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x][y - 1] != true && map[x][y] > map[x][y - 1])
				return new Vertex(x, y - 1);
		}
		
		// 아래
		if (direction.equals("D") && y + 1 <= downBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x][y + 1] != true && map[x][y] > map[x][y + 1])
				return new Vertex(x, y + 1);
		}

		return null;
	}
	
	// 주어진 방향으로 공사 가능한 경우 공사된 map 리턴, 불가능한 경우 null 리턴  
	public static int[][] findConstructedMap(int[][] map, boolean[][] visited, int x, int y, String direction, int numK) {
		int leftBound = 0;
		int rightBound = map[0].length - 1;
		int upBound = 0;
		int downBound = map.length - 1;
		
		int[][] map_ = new int[map[0].length][map.length];
		
		for (int i = 0; i < map_.length; i++) {
			for (int j = 0; j < map_[0].length; j++) {
				map_[j][i] = map[j][i];
			}
		}
				
		// 왼쪽
		if (direction.equals("L") && x - 1 >= leftBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x - 1][y] != true && map[x][y] > map[x - 1][y] - numK) {
				map_[x - 1][y] = map[x][y] - 1;
				return map_;
			}
		}
		
		// 오른쪽
		if (direction.equals("R") && x + 1 <= rightBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x + 1][y] != true && map[x][y] > map[x + 1][y] - numK){
				map_[x + 1][y] = map[x][y] - 1;
				return map_;
			}
		}
		
		// 위
		if (direction.equals("U") && y - 1 >= upBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x][y - 1] != true && map[x][y] > map[x][y - 1] - numK){
				map_[x][y - 1] = map[x][y] - 1;
				return map_;
			}
		}
		
		// 아래
		if (direction.equals("D") && y + 1 <= downBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x][y + 1] != true && map[x][y] > map[x][y + 1]  - numK){
				map_[x][y + 1] = map[x][y] - 1;
				return map_;
			}
		}

		return null;
	}
}

class Vertex {
	public int X;
	public int Y;
	
	public Vertex(int X_, int Y_) {
		this.X = X_;
		this.Y = Y_;
	}
}

(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_;
	}
}