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

접근 방법

main

1. 가장 처음에 세로 방향에 대해서 성능 검사를 통과할 수 있는지 확인한다. isTest()
2. 통과하지 못한다면 dfs() 실행

 

dfs()

• 약품을 투입하지 않는 경우, 약품을 투입하는 경우(A/B)로 나누어 모든 열에 대해 진행한다.
• 마지막 열에 도착했으면 isTest()로 성능 검사를 한다.
• 성능 검사에 통과했다면 약품 최소 투여 횟수를 갱신한다.
• 백트래킹으로 현재 파라미터의 약품 주입 횟수가 갱신된 최소 횟수를 넘었다면 더이상 탐색하지 않는다.

 

isTest()

• 가장 바깥의 반복문은 모든 열에 대해서 반복한다.
• 검사 통과를 위한 boolean 변수를 선언한다.
• 첫번째 값을 prev 변수에 저장한다
• 모든 행에 대한 반복문 시작
• 이전과 같다면 cnt 증가, 아니라면 cnt를 1로 돌려주고 이전값을 현재 값으로 갱신한다.
• 행을 탐색하면서 cnt가 K에 도달했다면 이 열은 성능검사에서 통과. 다음 열로 진행
• 하나의 열에 대해 모든 행 탐색이 끝났는데 false라면 그 열은 성능검사 통과 못함

 

import java.util.Scanner;

public class Solution {

	static int D, W, K, res;
	static int[][] map, copy;
	static boolean[] check;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			res = Integer.MAX_VALUE; // 약품 투입 최소 횟수

			D = sc.nextInt();
			W = sc.nextInt();
			K = sc.nextInt();

			// 0==A, 1==B
			map = new int[D][W];
			copy = new int[D][W];
			for (int i = 0; i < D; i++) {
				for (int j = 0; j < W; j++) {
					map[i][j] = copy[i][j] = sc.nextInt();
				}
			} // end input

			if (isTest()) {
				res = 0;
			} else {
				dfs(0, 0);
			}

			System.out.println("#" + tc + " " + res);
		}
		sc.close();
	}

	private static void dfs(int idx, int cnt) { // 검사 행, 용액 주입 횟수
		// 백트래킹
		if (cnt >= res)
			return;

		// 끝 행까지 dfs를 탔다면 반환
		if (idx == D) {
			// 모든 열이 K를 만족한다면 최소값 갱신
			if (isTest()) {
				res = Math.min(res, cnt);
			}
			return;
		}

		// 한 열에 대해서 idx를 행까지 검사

		// 지금 행을 안 바꾸는 경우
		dfs(idx + 1, cnt);

		// 현재 행을 A로 바꾸는 경우
		for (int j = 0; j < W; j++) {
			copy[idx][j] = 0;
		}
		dfs(idx + 1, cnt + 1);

		// 현재 행을 B로 바꾸는 경우
		for (int j = 0; j < W; j++) {
			copy[idx][j] = 1;
		}
		dfs(idx + 1, cnt + 1);

		// 원래대로 돌려줌
		for (int j = 0; j < W; j++) {
			copy[idx][j] = map[idx][j];
		}

	}

	private static boolean isTest() {
		for (int j = 0; j < W; j++) {
			boolean flag = false;
			int cnt = 1;
			int prev = copy[0][j];
			for (int i = 1; i < D; i++) {
				if (prev == copy[i][j]) {
					cnt++;
				} else {
					cnt = 1;
					prev = copy[i][j];
				}

				if (cnt == K) {
					flag = true;
					break; // 해당 열이 검사에서 통과함
				}
			}
			if (!flag)
				return false; // 한 열이라도 검사에서 통과하지 못하면 false 반환
		}
		return true; // 전부 탐색했을 때 통과된 상태
	}

}

스터디와 역량테스트 때문에 여러번 풀었던 문제였는데 풀때마다 풀이가 조금씩 달라지는 문제였다.

성능검사를 할 때 진행 중 성능검사에 통과하여 다음 열로 진행하는 경우와, 모든 행을 탐색하고 나서 이 행이 통과되는지를 확인하는 부분에서 디버깅이 오래 걸렸다.

또한, 용액을 주입할 때 다른 사람의 코드를 보며 깔끔하게 짜는 코드를 몇가지 확인했다.

• A, B에 대한 값을 final int로 선언하여 직관적으로 변수 관리하기
• 행의 크기만큼 배열 2개를 A, B값으로 전부 변경해두고 arr[idx] = A[idx]와 같이 관리하기

두번째 방법을 보고 나도 저렇게 짤걸!!! 소리없는 절규를 했다. W만큼 반복문을 돌릴 필요가 없을 뿐더러, 배열 값 임시저장해두고 dfs 다 돌았을때 = 연산자로 복귀만 시켜주면 되는 방법... 코드를 짜는 방법에 대해서도 다시 생각해보게 되었다.