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

SW Expert [모의 SW 역량테스트] 2112번 보호 필름 : 

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

 

 

지난 주 화요일에 스타트와 링크 문제를 풀면서 처음으로 조합 알고리즘을 공부했다.

그동안 스타트와 링크 문제 뿐 아니라 가르침 문제에서도 조합 알고리즘을 사용했다.

이번 보호 필름도 조합 알고리즘을 사용해서 풀게 되었다.

 

이번 문제에서는 총 7개의 함수를 작성했다.

그 중에서 메인이 되는 함수는 comb와 check 함수이다. 나머지 함수는 코드만 봐도 바로 알 정도로 간단한 함수이다.

 

comb 함수는 총 d개의 행 중에 r개를 뽑는 함수이다.

위에서 언급한 스타트와 링크 문제에서 사용한 comb 함수와 기본 틀은 같다.

길이 d짜리인 boolean 배열(comb)을 선언한 뒤 뽑은 index를 true로 변환한다.

check 함수는 comb 함수에서 뽑은 값들을 받아서 A나 B로 하나의 행을 채우면서 검사를 한다.

여기서 comb 함수에서 뽑은 값은 getSet 함수를 통해 check 함수로 넘겨지게 된다.

 

예를 들면 comb 함수에서 2, 5번 행이 선택 되었다고 하면,

2번과 5번을 (A, A), (A, B), (B, A), (B, B) 순서로 채우게 된다.

이런 방식으로 모든 경우의 수에 대하여 체크를 할 수 있다.

 

 

코드

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

public class Main {
    private static int d, w, k, answer;
    private static boolean[][] map;
    private static boolean[] comb;
    private static ArrayList<Integer> temp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        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 boolean[d][w];
            comb = new boolean[d];
            answer = 0;

            for (int i = 0; i < d; i++) { // 입력 : A -> false, B -> true
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    map[i][j] = st.nextToken().equals("1");
                }
            }

            if (!isFinish(map)) solution();
            System.out.println("#" + t + " " + answer);
        }
    }

    private static void solution() {
        for (int i = 1; i < d; i++) {
            comb(0, 0, i); // 조합 : nC1, nC2, ...
            if (answer != 0) break;
        }
    }

    private static void comb(int start, int depth, int r) { // 조합 nCr
        if (depth == r) { // r개 선택 완료
            check(getSet(), copy(map), 0);
            return;
        }
        for (int i = start; i < d; i++) {
            comb[i] = true;
            if (answer == 0) comb(i + 1, depth + 1, r);
            comb[i] = false;
        }
    }

    private static void check(ArrayList<Integer> set, boolean[][] map, int depth) {
        if (depth == set.size()) {
            if (isFinish(map)) answer = set.size();
            return;
        }
        fill(map, set.get(depth), false);
        check(set, map, depth + 1);
        fill(map, set.get(depth), true);
        check(set, map, depth + 1);
    }

    private static ArrayList<Integer> getSet() {
        temp = new ArrayList<>();
        for (int i = 0; i < d; i++) {
            if (comb[i]) temp.add(i);
        }
        return temp;
    }

    private static void fill(boolean[][] map, int i, boolean value) { // i번째 위치를 value로 채움
        for (int j = 0; j < w; j++) {
            map[i][j] = value;
        }
    }

    private static boolean[][] copy(boolean[][] map) { // 배열 깊은 복사
        boolean[][] result = new boolean[d][w];
        for (int i = 0; i < d; i++) {
            System.arraycopy(map[i], 0, result[i], 0, w);
        }
        return result;
    }

    private static boolean isFinish(boolean[][] map) { // 성능 검사를 통과하면 true
        for (int j = 0; j < w; j++) {
            int count = 1;
            boolean flag = false, target = map[0][j];
            for (int i = 1; i < d; i++) {
                if (map[i][j] == target) count++;
                else {
                    target = map[i][j];
                    count = 1;
                }
                if (count == k) {
                    flag = true;
                    break;
                }
            }
            if (!flag) return false;
        }
        return true;
    }
}