[SWEA/Java] 2112. 보호 필름

[SWEA/Java] 2112. 보호 필름

SW Expert Academy

---

문제 해석

D개의 층으로 구성된 W개의 열을 가진 보호 필름의 품질을 검사하는 문제다. 특정 열에서 K개의 연속된 층이 같은 성질을 보여야만 합격 기준을 만족한다. 이때, 필요한 최소한의 층만 약품 처리하여 모든 열이 K개의 연속된 같은 성질을 가지게 만드는 문제다.

풀이 과정

1. 기본적으로 모든 열이 이미 K개의 연속된 성질을 만족하는지 체크한다 (check() 메서드).
2. 만족하지 않는 경우, 조합을 사용하여 어떤 층을 약품 처리할지 결정한다 (combination() 메서드).
3. 결정된 층에 대해 0과 1의 약품을 각각 주입해 보며 조건을 만족하는지 검사한다 (recursive()와 injection() 메서드).
4. 최소한의 약품 처리로 모든 조건을 만족할 수 있는 경우를 찾으면 그 때의 처리 층의 수를 결과로 반환한다.

코드

package edu.ssafy.im.SWEA.D0.No2112;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
    private static int D, W, K; // 각각 보호 필름의 층 수, 열 수, 합격 기준 연속 층 수
    private static int[][] map, original; // 현재 맵 상태와 원래 맵 상태 저장
    private static int[] sel, rSel; // 약품 처리할 층 선택과 약품 종류 선택
    private static int ans; // 결과 저장 변수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int TC = Integer.parseInt(br.readLine()); // 테스트 케이스 수
        for (int T = 1; T <= TC; 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];
            original = new int[D][W];
            for (int i = 0; i < D; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < W; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    original[i][j] = map[i][j];
                }
            }
            sol(); // 솔루션 함수 실행
            sb.append("#").append(T).append(" ").append(ans).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void sol() {
        ans = 0;
        if (check()) return; // 기본 검사 통과 시 리턴

        for (int i = 1; i < K; i++) {
            sel = new int[i]; // 약품 처리할 층 선택
            rSel = new int[i]; // 선택된 층에 주입할 약품 종류 선택
            combination(0, 0); // 조합 실행
            if (ans != 0) return; // 결과가 나왔으면 리턴
        }

        ans = K; // K개 이상 약품 처리해야 한다면 K 반환
    }

    private static boolean check() { // 현재 맵 상태가 기준을 충족하는지 체크
        for (int y = 0; y < W; y++) {
            boolean flag = false;
            for (int x = 0; x < D - K + 1; x++) {
                int sum = 0;
                for (int nx = x; nx < x + K; nx++) {
                    sum += map[nx][y];
                }
                if (sum == 0 || sum == K) {
                    flag = true;
                    break;
                }
            }
            if (!flag) return false; // 하나라도 기준 충족 못하면 false
        }
        return true; // 모두 충족하면 true
    }

    private static void combination(int k, int v) { // 약품 처리할 층 조합 생성
        if (ans != 0) return; // 이미 결과가 있으면 리턴
        if (k == sel.length) {
            recursive(0); // 조합 완성되면 재귀적 약품 주입 시도
            return;
        }

        for (int i = 0; i < D; i++) {
            if ((v & (1 << i)) != 0) continue; // 이미 선택된 층은 건너뛰기
            sel[k] = i; // 층 선택
            combination(k + 1, v |= 1 << i); // 다음 층 선택을 위해 재귀 호출
        }
    }

    private static void recursive(int k) { // 약품 종류 조합 생성
        if (ans != 0) return; // 결과가 이미 있으면 리턴
        if (k == rSel.length) {
            injection(); // 약품 주입 시도
            return;
        }

        rSel[k] = 0; // 0 약품 주입
        recursive(k + 1); // 다음 층 약품 주입 시도
        rSel[k] = 1; // 1 약품 주입
        recursive(k + 1); // 다음 층 약품 주입 시도
    }

    private static void injection() { // 실제로 약품 주입하고 검사
        for (int i = 0; i < sel.length; i++) {
            for (int y = 0; y < W; y++) {
                map[sel[i]][y] = rSel[i]; // 약품 주입
            }
        }

        if (check()) { // 약품 주입 후 검사
            ans = sel.length; // 기준 충족하면 결과 저장
            return;
        }

        for (int i = 0; i < sel.length; i++) {
            map[sel[i]] = original[sel[i]].clone(); // 원래 상태로 복원
        }
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 주로 combination() 함수에서 조합을 생성하고, 각 조합에 대해 모든 열을 검사하는 check() 함수에서 결정된다. 각 단계에서 D개의 층 중 최대 K개를 선택하는 조합의 경우의 수와, 각 경우에 대해 W개의 열을 D-K+1번 검사하므로 최악의 경우 시간 복잡도는 𝑂((𝐷𝐾)×𝑊×(𝐷−𝐾+1))가 된다. 하지만, 실제로는 약품 처리 층 수가 적을 때 조기에 종료되는 경우가 많으므로, 평균적인 시간 복잡도는 이보다 훨씬 낮을 수 있다.

느낀점

이 문제는 조합과 재귀를 사용하여 가능한 모든 약품 처리 조합을 시도해보는 완전 탐색 문제다. 문제의 깊이를 이해하고, 이를 효과적으로 코드로 구현하는 과정에서 많은 것을 배울 수 있었다. 특히, 재귀 호출과 백트래킹을 사용하여 문제를 해결하는 방식은 다양한 문제에 응용 가능하며, 이를 통해 더 깊이 있는 알고리즘 설계 능력을 키울 수 있었다.