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

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.