[SWEA] 모의 SW 역량 테스트 2112번 보호 필름 (JAVA)

문제 출처 - SW Expert Academy

문제는 여기

SW Expert Academy

[문제] 

성능이 우수한 보호 필름을 제작하려고 한다.
보호 필름은 [Fig. 1]와 같은 엷은 투명한 막을 D장 쌓아서 제작된다.
막은 [Fig. 1]과 같이 동일한 크기를 가진 바(bar) 모양의 셀들이 가로 방향으로 W개 붙여서 만들어진다.
이렇게 제작된 필름은 두께 D, 가로 크기 W의 보호 필름이라고 한다.

각 셀들은 특성 A 또는 특성 B를 가지고 있다. 보호 필름의 성능은 셀들의 특성이 어떻게 배치됨에 따라 결정된다.
[Fig. 1]은 셀 6개를 이어서 만든 막의 단면이다.
[Fig. 2]는 셀 8개로 이루어진 엷은 막 6장을 쌓아서 만든 두께 6, 가로크기 8인 보호 필름의 단면이다.  A, B는 각 셀들이 가진 특성 A, 특성 B를 의미한다.

보호 필름의 성능을 검사하기 위해 합격기준 K라는 값을 사용한다.
충격은 보호 필름 단면의 세로 방향으로 가해지므로, 세로 방향 셀들의 특성이 중요하다. (충격방향은 [Fig. 3]의 빨간색 화살표 참조)
단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 된다.
[Fig. 3]과 같이 보호 필름의 단면이 주어지고 합격기준 K값이 3으로 주어지는 경우를 생각해 보자.(예제 입력 1번과 동일)
세로방향 ①, ②, ③, ⑤, ⑥, ⑦, ⑧번 위치에는 동일한 특성을 지닌 셀이 3개 이상 연속적으로 있다. ([Fig. 3]의 빨간색 사각형 참조)
하지만 ④번 위치는 동일한 특성을 지닌 셀이 3개 이상 연속적으로 있지 않으므로 성능검사를 통과할 수 없다.

성능검사에 통과하기 위해서 약품을 사용하여야 한다.
약품은 막 별로 투입할 수 있으며 이 경우 투입하는 막의 모든 셀들은 하나의 특성으로 변경된다.
특정 막에 약품 A를 투입하면 막 내의 모든 셀들이 특성 A로 변경되며, 약품 B를 넣게 되면 특성이 모두 특성 B로 변경된다.
[Fig. 4]는 세 번째 막에 약품 A를 투입하여 특성 A로 변경하고, 여섯 번째 막에 약품 B를 투입하여 특성 B로 변경시킨 경우이다.

약품 투입횟수 두 번으로 ①~⑧번까지의 모든 세로방향에 대해서 동일한 특성의 셀들이 연속적으로 3개 이상 있기 때문에 성능검사를 통과하였다. (합격기준 K=3)
[Fig. 3]의 경우 약품을 투입하여 성능검사를 통과시키는 방법은 여러 방법이 있을 수 있지만 투입횟수의 최소값은 2이다.
따라서 성능검사를 통과하기 위한 최소 약품투입 횟수는 2가 된다.
두께 D, 가로크기 W인 보호 필름 단면의 정보와 합격기준 K가 주어졌을 때, 약품 투입 횟수를 최소로 하여 성능검사를 통과할 수 있는 방법을 찾고,
이때의 약품 투입 횟수를 출력하라. ([Fig. 3] 예제의 경우 정답은 2가 된다.)
약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다.

[입력]

첫 줄에 총 테스트 케이스의 개수 T가 주어진다.
두 번째 줄부터 T개의 테스트 케이스가 차례대로 주어진다.
각 테스트 케이스의 첫 줄에는 보호 필름의 두께 D, 가로크기 W, 합격기준 K가 차례로 주어진다.
그 다음 D줄에 보호 필름 단면의 정보가 주어진다. 각 줄에는 셀들의 특성 W개가 주어진다. (특성A는 0, 특성B는 1로 표시된다.)

[출력]

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 “#x”로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 성능검사를 통과할 수 있는 약품의 최소 투입 횟수이다. 약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다.

 

 

---

[풀이]

1. 부분 집합을 이용해서 모든 선택지에 해당하는 곳을 선택한다.

2. 선택된 곳들을 dfs를 통해 탐색한다.

3. 탐색이 끝나고 유효성 검사를 한다.

4. 유효성 검사에서 통과를 하면 결괏값을 최솟값으로 갱신해주고, 아니라면 돌아간다.

5. 맵을 초기화 해주고 위 과정을 반복한다.

6. 결과값을 출력한다.

[접근]

1. 각 자리를 어떻게 선택할 것인지를 고민했다.

2. 선택하는 방법에서 아무 곳도 선택 안 해도 되고, 모든 곳을 선택해도 되는 것에서 부분 집합을 생각하였다.

3. 선택이 되면 해당하는 자리를 이용해 dfs탐색을 한다.

4. 각 행마다 체크해서 유효한지를 확인해준다.

5. 다 돌고 나면 맵을 초기화 해준다.

[코드]

package swet;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution_test_2112 {
	static int T; // 테케수
	static int D; // 행
	static int W; // 열
	static int K; // 통과기준
	static int result;
	static int map[][]; // map
	static int copy[][]; // map을 복구하기 위한 copy
	static boolean[] isSelected; // 부분집합에서 선택한 것을 나타낼 boolean배열

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			D = Integer.parseInt(st.nextToken()); // 행
			W = Integer.parseInt(st.nextToken()); // 열
			K = Integer.parseInt(st.nextToken()); // 통과기준
			
			map = new int[D][W];
			copy = new int[D][W];
			isSelected = new boolean[D];
			result = Integer.MAX_VALUE;
			
			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(br.readLine());
				
				for (int j = 0; j < W; j++) {
					map[i][j] = copy[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			if (check()) {
				System.out.println("#" + t + " 0");
			}
			else {
				subset(0);
				System.out.println("#" + t + " " + result);
			}
			
		}
	}
	
	// 부분집합으로 어디에 약물을 투여할 지 선택
	public static void subset(int cnt) {
		if (cnt == D) {
			dfs(isSelected, 0, 0);
			mapReset();
			return;
		}
		isSelected[cnt] = true;
		subset(cnt+1);
		isSelected[cnt] = false;
		subset(cnt+1);
	}
	
	// 각 행마다 약물을 투여해보고 결과구하기
	public static void dfs(boolean[] check, int cnt, int index) {
		if (cnt >= result) // 현재 결과값보다 크면 더 탐색할 필요가 없음
			return;
		
		if (index == D) {
			if (check()) { // 유효성 검사하고
				result = Math.min(result, cnt); // 통과하면 최소값으로 결과 갱신
			}
			return;
		}
		
		if (check[index]) {
			// A로 약물 투여
			Arrays.fill(map[index], 0);
			dfs(check, cnt + 1, index + 1);
			
			// B로 약물 투여
			Arrays.fill(map[index], 1);
			dfs(check, cnt + 1, index + 1);
		}
		else {
			dfs(check, cnt, index + 1);
		}
	}

	// 행을 기준으로 k만큼의 구역이 있는지를 확인
	public static boolean check() { 
		for (int i = 0; i < W; i++) {
			int cnt = 1; // 시작점을 포함하기 때문에 1
			int start = map[0][i]; // 시작점을 기준
			boolean pass = false;
			
			for (int j = 1; j < D; j++) {
				if (start == map[j][i]) { // 시작과 같으면
					cnt++; // 수를 증가
				}
				else { // 다르면
					start = map[j][i]; // 시작점을 바꿔주고
					cnt = 1; // cnt를 1로 초기화
				}
				
				if (cnt == K) { // 합격 기준을 넘어가면 더 체크할 필요가 없음
					pass = true;
					break;
				}
			}
			if (pass == false) // 하나라도 만족하지 않으면 실패기 때문에 돌아가기
				return false;
		}
		return true;
	}
	
	// 맵 초기화하기
	public static void mapReset() {
		for (int i = 0; i < D; i++) {
			for (int j = 0; j < W; j++) {
				map[i][j] = copy[i][j];
			}
		}
	}
}

[실수]

1. dfs를 돌면서 map을 초기화해줬는데 이렇게 하면 아직 다 끝나지도 않았는데 map이 계속 초기화되어 값이 이상하게 변한다. 이를 dfs가 끝나고 돌아오면 그때 map을 초기화해주는 것으로 해결했다.