[SWEA 2112번] 보호 필름 :: 늦깎이 IT

[SWEA 2112. [모의 SW 역량테스트] 보호 필름 URL]

1. 총 3가지의 경우를 생각할 수 있다.

1) 현재 행을 그대로 두는 경우

2) 현재 행에 A약을 투입하는 경우

3) 현재 행에 B약을 투입하는 경우

2. 위의 세 가지 경우를 생각하며 DFS 탐색을 진행한다.

DFS 매개변수로는, 이전 필름의 상태(prev), 시약을 투입한 횟수(numOfInject), 필름의 두께(depth)이다.

현재 행을 그대로 두는 경우에는 numOfInject의 수는 변함이 없고, 현재 행에 약을 투입하는 경우에만 1을 증가

시켜 DFS탐색을 진행한다. 현재 행(depth)에 시약을 투입할 경우 필름의 상태를 변경한 뒤, DFS의 매개변수로

넘겨준다.

3. 성능검사 통과

isPossible() 메소드를 참고하기 바란다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.concurrent.LinkedBlockingDeque;
 
public class Solution {
 
    public static int D, W, K, tCase, ans;
    public static int[][] map;
    public static int[] dirX = new int[] { 0, 0, 1, -1 }; // 동서남북
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        tCase = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= tCase; t++) {
 
            StringTokenizer st = new StringTokenizer(br.readLine());
            D = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            ans = Integer.MAX_VALUE;
            map = 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());
                }
            }
 
            dfs(map, 0, 0);
            System.out.println("#" + t + " " + ans);
        }
    }
 
    public static void dfs(int[][] prev, int numOfInject, int depth) {
 
        if (numOfInject >= ans)
            return;
 
        if (depth >= D) {
            if (isPossible(prev)) {
                ans = Math.min(ans, numOfInject);
            }
            return;
        }
 
        int[][] temp = new int[D][W];
        for (int i = 0; i < D; i++)
            temp[i] = Arrays.copyOf(prev[i], prev[i].length);
 
        dfs(temp, numOfInject, depth + 1);
 
        Arrays.fill(temp[depth], 0);
        dfs(temp, numOfInject + 1, depth + 1);
 
        Arrays.fill(temp[depth], 1);
        dfs(temp, numOfInject + 1, depth + 1);
 
    }
 
    public static boolean isPossible(int[][] map) {
 
        for (int j = 0; j < W; j++) {
            boolean flag = false;
            for (int i = 0; i <= D - K; i++) {
 
                flag = true;
 
                for (int k = 1; k < K; k++) {
 
                    if (map[i][j] != map[i + k][j]) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    break;
            }
            if (!flag)
                return false;
        }
        return true;
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < D) && (col >= 0 && col < W);
    }
 
    public static void showMap(int[][] map) {
        for (int i = 0; i < D; i++) {
            for (int j = 0; j < W; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}