SWEA 모의 2112 보호필름

SWEA 모의 2112 보호필름

 

 

문제링크

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

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

핵심 컨셉

고려사항

 * 보호 필름은 가로 길이 W * 두께 D로 구성된 이차원 배열로 표현되며 이차원 배열의 각 칸들은 셀이라는 개념으로 사용됨
  -- 셀은 A 또는 B(지도 상에는 0,1로 표시됨)라는 특성을 가짐
  -- 이 보호필름에 세로 방향으로 가해지는 힘을 견디기 위해 세로로 W개의 셀이 모두 같은 특성을 지녀야 함

 * 약품 처리를 해서 셀의 특성을 바꾸는데 한 줄이 통으로 바뀜 --> 그럼 어디다 약품 처리를 해야할까? 알수없으면 완탐이다.
  -- 약품 처리는 할수도 있고 A로 또는 B로 할 수 있기 때문에 각 필름에서는 3가지의 선택지가 존재
  -- 탐색은 어떤 순서로 선택하는지에 따라 결과가 달라지기 때문에 순열이 적합
  -- 약품 투입으로 행 전체가 바뀌는데 실제 맵을 바꾸기 보다는 바꿀 값들을 저장 후 재사용하는 것이 부담이 적다.

입력사항

 * 보호 필름의 두께 D는 3이상 13이하의 정수이다. (3≤D≤13)
 * 보호 필름의 가로크기 W는 1이상 20이하의 정수이다. (1≤W≤20)
 * 합격기준 K는 1이상 D이하의 정수이다. (1≤K≤D)
 * 셀이 가질 수 있는 특성은 A, B 두 개만 존재

출력사항

 * 성능검사를 통과할 수 있는 약품의 최소 투입 횟수 출력
 * 만약 약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/FxIHhrtLZdo

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.모의;

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

public class SWEA_모의_2112_보호필름 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();

    static int R; // 보호 필름 폭 W는 1이상 20이하의 정수이다. (1≤W≤20)
    static int C; // 보호 필름의 두께 D는 3이상 13이하의 정수이다. (3≤D≤13)
    static int K; // 합격기준 K는 1이상 D이하의 정수이다. (1≤K≤D)
    static int Min; // 최소 투약 회수
    static int[][] map;

    // 약품의 투여 여부를 구성하는 부분집합
    static int[] injectResult; // -1: 투여하지 않음, 0: a 투여, 1: b 투여

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));

        int T = Integer.parseInt(input.readLine());
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer tokens = new StringTokenizer(input.readLine());

            R = Integer.parseInt(tokens.nextToken()); // 보호 필름의 두께 (3≤D≤13)
            C = Integer.parseInt(tokens.nextToken()); // 보호 필름의 가로크기 (1≤W≤20)
            K = Integer.parseInt(tokens.nextToken()); // 합격기준 K (1≤K≤D)

            map = new int[R][C];
            injectResult = new int[R];
            for (int r = 0; r < R; r++) {
                tokens = new StringTokenizer(input.readLine());
                for (int c = 0; c < C; c++) {
                    map[r][c] = Integer.parseInt(tokens.nextToken());
                }
            }
            // 입력 처리 완료
            Min = Integer.MAX_VALUE;
            dfs(0, 0);// 행과 주입 회수

            output.append("#").append(tc).append(" ").append(Min).append("\n");
        }
        System.out.println(output);
    }

    /**
     * @param row 행번호
     * @param inject 약품 투여 회수
     */
    public static void dfs(int row, int inject) {
        // 최소값을 넘어가면 의미 없다.
        if (inject >= Min) {
            return;
        }
        // 맨 마지막에 도달하면 체크하기
        if (row == R) {
            if (check()) {
                Min = Math.min(Min, inject);
            }
            return;
        }

        for (int i = -1; i < 2; i++) {
            injectResult[row] = i;
            // 약품 주입을 안하는 경우 - 주입 회수는 유지
            if (i == -1) {
                dfs(row + 1, inject);
            }
            // 약품 주입 처리하는 경우 - 주입 회수 증가
            else {
                dfs(row + 1, inject + 1);
            }
        }
    }

    static boolean check() {
        int cnt = 0;// 연속된 셀을 세는 카운트
        int cur, next;// 검사할 현재 셀과 다음 셀
        for (int c = 0; c < C; c++) {
            cnt = 1;
            for (int r = 0; r < R - 1; r++) {// 다음 행까지 검사할 꺼다.
                // 기본적으로는 맵에 있는 값을 가져다 쓴다.
                cur = injectResult[r] == -1 ? map[r][c] : injectResult[r];
                next = injectResult[r + 1] == -1 ? map[r + 1][c] : injectResult[r + 1];// 다음 행과 비교

                if (cur == next) {// 연속된 경우
                    cnt++;
                    if (cnt >= K) {
                        break;
                    }
                } else {
                    cnt = 1;
                }
            }
            // 이번 컬럼에서 실패 --> 실패
            if (cnt < K) {
                return false;
            }
        }
        return true;
    }


    static String src = "10\r\n" +
                        "6 8 3\r\n" +
                        "0 0 1 0 1 0 0 1\r\n" +
                        "0 1 0 0 0 1 1 1\r\n" +
                        "0 1 1 1 0 0 0 0\r\n" +
                        "1 1 1 1 0 0 0 1\r\n" +
                        "0 1 1 0 1 0 0 1\r\n" +
                        "1 0 1 0 1 1 0 1\r\n" +
                        "6 8 3\r\n" +
                        "1 1 1 1 0 0 1 0\r\n" +
                        "0 0 1 1 0 1 0 1\r\n" +
                        "1 1 1 1 0 0 1 0\r\n" +
                        "1 1 1 0 0 1 1 0\r\n" +
                        "1 1 0 1 1 1 1 0\r\n" +
                        "1 1 1 0 0 1 1 0\r\n" +
                        "6 8 4\r\n" +
                        "1 1 0 0 0 1 1 0\r\n" +
                        "1 0 1 0 0 1 1 1\r\n" +
                        "0 1 0 0 1 1 0 0\r\n" +
                        "1 0 1 0 0 0 0 0\r\n" +
                        "1 1 0 0 0 0 0 0\r\n" +
                        "1 0 0 0 1 1 1 1\r\n" +
                        "6 4 4\r\n" +
                        "1 1 0 0\r\n" +
                        "0 1 0 1\r\n" +
                        "0 0 0 1\r\n" +
                        "1 1 1 1\r\n" +
                        "1 1 0 1\r\n" +
                        "1 0 1 0\r\n" +
                        "6 10 3\r\n" +
                        "0 1 0 0 0 1 0 0 1 1\r\n" +
                        "0 1 1 0 0 1 0 0 1 0\r\n" +
                        "0 1 0 0 1 0 1 1 1 1\r\n" +
                        "0 0 0 0 0 1 1 1 1 0\r\n" +
                        "0 1 0 0 1 1 1 1 1 1\r\n" +
                        "1 0 0 0 1 1 0 0 1 1\r\n" +
                        "6 6 5\r\n" +
                        "0 0 0 0 0 0\r\n" +
                        "0 0 0 0 0 0\r\n" +
                        "0 0 0 0 0 0\r\n" +
                        "0 0 0 0 0 0\r\n" +
                        "0 0 0 0 0 0\r\n" +
                        "0 0 0 0 0 0\r\n" +
                        "6 6 4\r\n" +
                        "1 1 1 1 1 1\r\n" +
                        "0 0 0 0 0 1\r\n" +
                        "0 1 1 1 0 1\r\n" +
                        "0 1 0 1 0 1\r\n" +
                        "0 1 0 0 0 1\r\n" +
                        "0 1 1 1 1 1\r\n" +
                        "8 15 3\r\n" +
                        "0 1 1 0 0 1 1 0 1 1 0 0 0 0 0\r\n" +
                        "1 0 0 0 1 1 0 0 0 0 0 1 0 1 1\r\n" +
                        "1 1 0 1 0 1 0 1 0 1 0 1 0 0 0\r\n" +
                        "0 1 1 1 0 0 1 0 0 0 0 1 0 0 0\r\n" +
                        "0 0 0 0 0 0 1 0 0 0 1 1 0 0 1\r\n" +
                        "1 0 1 0 0 1 0 1 1 1 1 0 1 1 1\r\n" +
                        "0 0 0 0 0 1 1 1 0 0 0 0 0 1 0\r\n" +
                        "0 0 1 0 1 1 0 1 1 0 0 0 1 0 0\r\n" +
                        "10 20 4\r\n" +
                        "1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 0 1\r\n" +
                        "1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0\r\n" +
                        "1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0\r\n" +
                        "0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0\r\n" +
                        "0 1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 1 1 1\r\n" +
                        "1 0 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0\r\n" +
                        "0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1\r\n" +
                        "1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 1 0\r\n" +
                        "0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 1\r\n" +
                        "0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0\r\n" +
                        "13 20 5\r\n" +
                        "1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0\r\n" +
                        "1 1 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0\r\n" +
                        "1 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 0\r\n" +
                        "0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1\r\n" +
                        "0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1\r\n" +
                        "0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1\r\n" +
                        "0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0\r\n" +
                        "1 1 1 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 1\r\n" +
                        "0 1 1 1 1 0 0 0 1 1 0 1 0 0 0 0 1 0 0 1\r\n" +
                        "0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1\r\n" +
                        "0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0\r\n" +
                        "0 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0\r\n" +
                        "0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0\r\n" +
                        "";
}