[ SWEA, 모의 SW 역량테스트 ] 2112번 보호 필름 (Java 자바)

🔗 문제 링크: SWEA 2112번 - 보호 필름

 

문제 개요

• 문제: 보호 필름의 단면(세로 D, 가로 W)이 주어질 때, 성능 검사 통과 조건(모든 열에 동일 특성 셀이 K개 이상 연속)이 만족되도록

최소한의 약품 처리(행 단위 전체 변경) 횟수를 구하는 문제.

• 조건:

• 약품 처리 시 해당 행의 모든 셀이 A(1) 또는 B(2)로 변경됨

• 0번 약품 처리 없이 원래 상태에서 성능 검사가 통과하면 0 출력

• 제한: D 최대 13, W 최대 20으로 완전 탐색(DFS, 백트래킹)로 해결 가능하다. 💡

---

해결 전략

1. DFS & 백트래킹 🚀

• 각 행마다 약품 처리를 할지 말지 결정하는 순열(조합) 탐색을 진행한다.

• 0번 처리(약품 미처리), 1번(A 처리), 2번(B 처리) 중 선택.

2. 성능 검사 함수 (evaluate) 🔍

• 모든 열에 대해, 연속된 동일 특성 셀이 K개 이상 있는지 검사하여 통과 여부를 반환한다.

3. 최소 약품 처리 횟수 갱신 ⏱

• DFS 도중 현재 사용한 약품 처리 횟수가 기존 최솟값보다 많으면 가지치기를 진행한다.

 

코드 설명

• dfs 함수:

• dfs(int[] condArr, int cur, int usedCnt) 함수에서,

• condArr 배열은 각 행에 대해 처리 상태(0: 미처리, 1: A 처리, 2: B 처리)를 저장한다.

• cur는 현재 행, usedCnt는 현재까지 사용한 약품 처리 횟수.

• 기저 조건: 모든 행을 결정한 경우, 성능 검사 함수로 통과 여부를 확인 후 최소 횟수를 갱신한다. ✔️

• 가지치기: usedCnt >= result 인 경우 더 진행하지 않는다.

• evaluate 함수:

• 각 열을 순회하며, 연속된 동일 특성의 셀 수를 센다.

• 한 열이라도 K개 미만이면 실패로 판단한다.

• 백트래킹:

• DFS 호출 후 condArr를 원래 상태로 복원하여 다른 경우의 수를 탐색한다.

 

package BruteForceSearch;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;

/*
 * SWEA 모의 SW 역량테스트 [ 보호 필름 ]
 * 문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu
 * 
 * 목표: 모든 열에 대해 연속된 동일 특성 셀이 K개 이상 있도록 약품 처리를 최소 횟수로 진행
 * 특징: 약품 처리는 행 단위로 A 또는 B로 전체 변경 가능 (최대 13행)
 * 알고리즘: DFS, 백트래킹
 */

class SWEA_EX_2112 {
    static int D, W, K;
    static int result;
    static int[][] map;
    
    // DFS를 위한 배열: condArr[i]가 0이면 미처리, 1이면 A 처리, 2이면 B 처리
    static void dfs(int[] condArr, int cur, int usedCnt) {
        // 가지치기: 이미 사용한 약품 횟수가 최소값 이상이면 종료
        if (usedCnt >= result) return;
        
        // 기저 조건: 모든 행의 상태를 결정한 경우
        if (cur == D) {
            if (evaluate(condArr)) {
                result = Math.min(result, usedCnt);
            }
            return;
        }
        
        // 원래 상태 유지: 약품 처리 없이 진행
        dfs(condArr, cur + 1, usedCnt);
        
        // 임시 상태 저장 (백트래킹을 위해)
        int backup = condArr[cur];
        
        // A 처리 (1)
        condArr[cur] = 1;
        dfs(condArr, cur + 1, usedCnt + 1);
        
        // B 처리 (2)
        condArr[cur] = 2;
        dfs(condArr, cur + 1, usedCnt + 1);
        
        // 백트래킹: 원래 상태로 복원
        condArr[cur] = backup;
    }
    
    // 성능 검사 함수: 각 열에 대해 연속된 동일 특성의 셀이 K개 이상 있는지 확인
    static boolean evaluate(int[] condArr) {
        // 각 열을 검사
        for (int j = 0; j < W; j++) {
            int count = 0;
            int prev;
            // 첫 행의 값: 약품 처리가 되었으면 condArr에 따른 값, 미처리이면 원래 값
            if (condArr[0] != 0) prev = condArr[0];
            else prev = map[0][j];
            count = 1;
            
            // 두 번째 행부터 검사
            for (int i = 1; i < D; i++) {
                int curVal = (condArr[i] != 0) ? condArr[i] : map[i][j];
                if (curVal == prev) count++;
                else {
                    prev = curVal;
                    count = 1;
                }
                // 연속된 셀이 K개 이상이면 다음 열로 바로 넘어감
                if (count >= K) break;
            }
            // 한 열이라도 조건을 만족하지 못하면 false 반환
            if (count < K) return false;
        }
        return true;
    }
    
    public static void main(String[] args) throws IOException {
        // 입출력 설정
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            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];
            
            for (int i = 0; i < D; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < W; j++) {
                    // 원래 문제에서는 특성이 1 또는 2로 주어지므로, 그대로 사용
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            // 초기 상태에서 성능검사를 통과하면 약품 처리 없이 0 출력
            if (evaluate(new int[D])) {
                sb.append("#").append(t).append(" ").append(0).append("\n");
            } else {
                result = Integer.MAX_VALUE;
                int[] condArr = new int[D];  // 모든 행은 처음에 0 (미처리)
                dfs(condArr, 0, 0);
                sb.append("#").append(t).append(" ").append(result).append("\n");
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}