SWEA 2112 보호필름

백트래킹

가지치기를 잘 해야 시간초과가 나지 않는다

• 한 열이 실패하면 그 경우는 무조건 실패다 → return false
• 한 열에서 k개 이상이 되면 그 열은 성공이다 → continue loop 해서 다음 열 탐색으로 넘어가자
• 0개부터 개수를 늘려가며 투여하므로 앞에서 답이 나왔다면 (ans≠-1) break하고 출력한다

알고리즘

1. 어떤 행에 약품을 투여할지 조합으로 정한다 (0개 ~h-1개)
   - h-1개까지 해서 안 되면 h개 투여해야하는 거니까 예외처리로 출력해준다
   - 새로운 dfs마다 memcpy를 해준다

2. 0개부터 개수를 늘려가며 투여하므로 앞에서 답이 나왔다면 (ans≠-1) break하고 출력한다

3. 조합을 돌리면서 재귀 전 insert, 재귀 후 delete로 약품 투여를 처리해준다

4. r개를 다 뽑았다면 조건에 맞는지 확인해준다
   - 위에 설명한 가지치기 적용
   - 여기서 큐나 스택을 쓰면 시간초과가 난다고 한다 (연산에 오버헤드가 있는 듯)

오답노트

1. 전 셀과 다를 때 cnt를 0이 아니라 1로 만들어줘야 한다!

```java
loop: for(int j=0; j<w; j++) {
            int cnt = 1;
            int type = map[0][j];
            for(int i=1; i<h; i++) {
                if(map[i][j]==type) {
                    cnt++;
                    // 이미 기준치 만족 
                    if(cnt>=success) continue loop;
                } else {
                    cnt = 1; // cf) cnt=0; => 틀린 코드
                    type = map[i][j];
                }
            }
```

위의 코드는 조건 확인을 하는 check()함수의 일부다

한 열이 A A B B B 처럼 돼 있을 때 B로 바뀔 때 cnt를 0으로 초기화 해 버렸다

이미 B 한 칸을 세고 넘어가는 거니까 cnt=1로 해줘야 맞다

2. k=1인 경우 예외처리 (아래 설명)

히든 테케

k=1인 경우 무조건 0을 출력해야 한다

⇒ 예외처리를 해서 맞을 수 있었다

1
5 1 1
0
1
0
1
0

 

전체 소스코드

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

public class Solution {
    static int h, w, success;
    static int[][] origin;
    static int[][] map;
    static int ans;

    static void init() {
        ans = -1;
        map = new int[h][w];
        origin = new int[h][w];
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            h = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            success = Integer.parseInt(st.nextToken());
            init();
            for (int i = 0; i < h; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    origin[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            if(success==1) {
                System.out.println("#"+tc+" "+0); 
                continue;
            }
            // 0개 ~ h개까지 조합 뽑기
            for (int i = 0; i < h; i++) {
                memcpy();
                dfs(0, i, 0);
                if(ans!=-1) break;
            }
            if(ans!=-1)
                System.out.println("#" + tc + " "+ans);
            else
                System.out.println("#"+tc+" "+h);
        }
    }
// r개 뽑는 조합
    static void dfs(int depth, int r, int now) { 
        if (depth == r) {
            //System.out.println(Arrays.toString(pick));
            boolean flag = check();
            if(flag) ans = r;
            return;
        }

        for (int type = 0; type < 2; type++) {
            for (int i = now; i < h; i++) {
                insert(i, type);
                dfs(depth + 1, r, i + 1);
                delete(i);
            }
        }
    }
 // 통과할 수 있을까?
    static boolean check() {
        loop: for(int j=0; j<w; j++) {
            int cnt = 1;
            int type = map[0][j];
            for(int i=1; i<h; i++) {
                if(map[i][j]==type) {
                    cnt++;
                    // 이미 기준치 만족 
                    if(cnt>=success) continue loop;
                } else {
                    cnt = 1;
                    type = map[i][j];
                }
            }
            // 한 줄이라도 틀림 
            return false;
        }
        return true;
    }
// 약품 투여
    static void insert(int height, int type) { 
        for (int i = 0; i < w; i++) {
            map[height][i] = type;
        }
    }
// 약품 거두기(?)
    static void delete(int height) { //
        for (int i = 0; i < w; i++) {
            map[height][i] = origin[height][i];
        }
    }
// 오리지날 맵 복사...... 왜 자바엔 이차원 memcpy가 없을까 ㅠ
    static void memcpy() {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                map[i][j] = origin[i][j];
            }
        }
    }
}