[Java] SWEA 보호 필름

1. 문제 분석

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu 

SW Expert Academy

보호필름의 강도를 체크하는 문제다. 특정 요소가 K만큼 반복되면 그 한줄은 통과가 되는 것이다.

모든 필름에는 강제로 특성을 주입할 수 있다. 주입을 안 할 수도 있고 최소 투입 횟수를 구하는 문제다.

 

먼저 생각해볼 것은 주입을 어떤식으로 판단할지가 된다.

투입 횟수의 최솟값을 구하는 것인데 우리는 주어진 조건이 딱히 없으니 완전탐색을 사용한다.

 

그렇다면 완전탐색을 어떤식으로 구할까? 바로 부분집합이다.

투입했을 때 -1, A특성 주입은 0, B특성 주입은 1로 필름의 높이만큼의 배열을 만들어 주었다.

-1, 0, 1을 뽑는 것인데 중복이 가능하고 필름의 높이까지 뽑아주면 된다.

 

뽑은 횟수가 필름의 높이만큼 된다면 주입한 필름이 유호한지 확인해준다.

만약 높이가 4, 필름의 주입여부가 [-1, -1, 0, 1]이라면 첫번째, 두번째는 그대로, 세번째는 모두 A, 네번째는 모두 B가 된다.

이건 코드로 설명하겠다.

 

검사가 통과되면 최솟값을 갱신해주고 만약 안된다면 0을 넣어주면 된다.

2. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    static int answer;
    static int width, height, pass;
    static int[][] film;
    static int[] set;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());

        for (int c = 1; c <= tc; c++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            answer = Integer.MAX_VALUE;
            height = Integer.parseInt(st.nextToken());
            width = Integer.parseInt(st.nextToken());
            pass = Integer.parseInt(st.nextToken());

            film = new int[height][width];
            set = new int[height];

            for (int i = 0; i < height; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < width; j++) {
                    film[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            dfs(0,0);
            if (answer == Integer.MAX_VALUE) {
                answer = 0;
            }
            System.out.println("#" + c + " " + answer);
        }
    }

    //3가지 숫자로 높이만큼의 크기를 가진 부분집합을 만드는 것
    //저장할 숫자: 투약횟수, 전부다 돌았을 때 검사할 것
    static void dfs(int count, int row) {

        //현재 투약 횟수가 최소 투약 횟수보다 크다면 할 필요가 없다.
        if(count >= answer){
            return;
        }

        //부분집합을 전부 뽑았다면 검사를 진행
        if(row == height){
            if(check()){
                answer = Math.min(answer, count);
            }
            return;
        }

        for (int i = -1; i < 2; i++) {
            set[row] = i;
            if (i == -1) dfs(count, row + 1);
            else dfs(count + 1, row + 1);
        }
    }

    static boolean check(){
        int passCount = 0;
        for(int i = 0; i<width; i++){
            int attrCount = 1;
            for(int j = 0; j<height - 1; j++){
                int first = set[j] == -1 ? film[j][i] : set[j];
                int second = set[j+1] == -1? film[j+1][i] : set[j+1];

                if(first == second){
                    attrCount++;
                    if(attrCount == pass){
                        passCount++;
                        break;
                    }
                }else{
                    attrCount = 1;
                }
            }
        }
        return passCount == width;
    }
}

check를 통해 검사를 해주었고 set이 -1이면 자기 자신, 아니면 set에 있는 배열값을 따른다.

필자는 만약 조건이 틀리면 1로 초기화를 해야하는데 0을 초기화해서 조금 꼬였다.

 

또한 시간초과가 나는 곳이 있어 dfs 코드내에 return하는 조건과 check 코드내에 pass가 만족하면 바로 break를 넣어주었다.

3. 마무리

보충시간에 풀었던 문제를 나만의 방법으로 풀려다가 포기했다.

DFS라고 해서 반드시 백트래킹을 하는것이 아니고 단순히 사용해도 된다는 것을 배웠다.