정범의 프로그래밍 블로그 입니다.

5 분 소요

1. 핵심 개념 및 근거

핵심 알고리즘: 백트래킹

  • 사용 이유: 각 행(두께)에 대해 ‘약품을 처리하지 않음’, ‘약품 A 주입’, ‘약품 B 주입’이라는 3가지 선택지가 존재합니다. 모든 경우를 탐색하되, 이미 찾은 최솟값보다 투입 횟수가 많아지면 탐색을 중단(가지치기)하기 위해 사용합니다.
  • 제약사항 기반 선택: 보호 필름의 두께 D가 최대 13으로 매우 작습니다. 3^13은 약 159만 정도로, 각 경우마다 합격 기준 K 를 통과하는지 검사하는 시뮬레이션을 수행하기에 충분한 범위입니다.
  • 시간 복잡도
    • 최악의 경우: O(3^D * W * D) 입니다.
    • 하지만, 가지치기를 통해 탐색 범위를 줄일 수 있습니다.


2. 추론 과정

  • 키워드1: “최소 투입 횟수”
    • 보통 최솟값을 구할 때는 BFS나 백트래킹을 고려합니다. 하지만 이 문제는 상태의 전이보다 ‘조합’의 성격이 강하므로 백트래킹이 적합합니다.
  • 키워드2: “두께 D(3~13), 가로 W(1~20), 합격 기준 K(1~D)”
    • D가 매우 작다는 점이 결정적인 힌트입니다. 지수 시간 복잡도를 가진 알고리즘도 통과할 수 있음을 암시합니다


3. 설계 및 접근

  1. 합격 여부 검사 (Check 함수):
    • 모든 열(W)에 대해 세로로 연속된 동일 시약(0 또는 1)이 K개 이상 존재하는지 확인합니다.
    • 한 열이라도 통과하지 못하면 그 필름은 불합격입니다.
  2. 재귀 호출 (DFS):
    • dfs(행 인덱스, 약품 투입 횟수) 형태로 설계합니다.
    • 선택지 1: 약품 투입 안 함 -> dfs(idx + 1, count)
    • 선택지 2: 약품 A 투입 -> 해당 행을 0으로 변경 후 dfs(idx + 1, count + 1) -> 원상복구
    • 선택지 3: 약품 B 투입 -> 해당 행을 1으로 변경 후 dfs(idx + 1, count + 1) -> 원상복구
  3. 가지치기 (Pruning):
    • 현재 count가 이미 발견된 min_ans보다 크거나 같다면 더 이상 탐색할 필요가 없습니다.


4. 예시 시뮬레이션

  • 상황: D = 3, K = 3
  • 초기 상태: [A, B, A] -> Check() 실패.
  • 1차 탐색 (1행에 A 주입): [A, B, A] -> [A, A, A].
  • 검사: 세로 열을 보니 A가 3개 연속됨 -> 합격
  • 결과: 최소 투입 횟수 1 출력.


5. 주의 사항

  • 실수 포인트: 약품을 주입한 뒤 다음 재귀에서 돌아왔을 때, 배열을 원래 상태로 복구(Backtrack)하는 과정을 잊으면 안 됩니다.
  • 성능 최적화: K=1인 경우는 검사할 필요 없이 무조건 0입니다. 또한, dfs 시작 전 원본 배열이 합격 기준을 통과하는지 먼저 체크하면 좋습니다.


6. 코드 풀이

6.1 합격 여부 검사 (check 함수)

연속성 확인

for (int r = 1; r < D; r++) {
    if (map[r][c] == map[r - 1][c]) {
        count++;
    } else {
        count = 1;
    }
 
    if (count >= K) {
        valid = true;
        break;
    }
}
  • 비교 방식: 현재 행과 이전 행의 값을 비교합니다.
  • 카운팅: 비교한 값이 같으면 count를 1 증가시키고, 다르면 다시 1로 초기화합니다.
  • 성공 지점: count가 K에 도달하는 순간, 해당 열은 더 볼 필요 없이 “합격” 입니다.

check 함수 전체 코드

private static boolean check() {
        // 모든 열(W)을 검사
        for (int c = 0; c < W; c++) {
            boolean valid = false;
            int count = 1; // 연속된 개수 (자기 자신 포함 1부터 시작)
 
            for (int r = 1; r < D; r++) {
                if (map[r][c] == map[r - 1][c]) {
                    count++;
                } else {
                    count = 1;
                }
 
                if (count >= K) {
                    valid = true;
                    break;
                }
            }
 
            // 단 한 열이라도 기준을 충족하지 못하면 바로 false
            if (!valid)
                return false;
        }
        return true;
    } // check 종료

6.2 재귀 호출 (DFS)

 static void dfs(int level, int cnt) {
 
        // 가지치기
        if (cnt >= result)
            return;
 
        // 종료 조건
        if (level == D) {
 
            if (check()) {
                result = cnt;
            }
 
            return;
        }
 
        // 미선택
        dfs(level + 1, cnt);
 
        // 원복 배열
        int temp[] = map[level].clone();
 
        // A 선택
        for (int i = 0; i < W; i++) {
            map[level][i] = 0;
        }
 
        // 다음 행 이동
        dfs(level + 1, cnt + 1);
 
        // B 선택
        for (int i = 0; i < W; i++) {
            map[level][i] = 1;
        }
 
        // 다음 행 이동
        dfs(level + 1, cnt + 1);
 
        // 백트래킹
        map[level] = temp;
 
    } // dfs 종료

6.3 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int D, W, K; // 보호 필름의 두께, 보호 필름의 가로크기, 합격 기준
    static int map[][]; // 보호 필름 단면 정보
    static int result; // 약품의 최소 투입 횟수
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine());
 
        // tc 수행
        for (int tc = 1; tc <= T; tc++) {
 
            // D, W K 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            D = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            // 초기화
            map = new int[D][W];
            result = K;
 
            // 보호 필듬 단면 정보 입력
            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());
                }
            }
             
            // 처리
            if(K==1) {
                sb.append("#"+tc+" "+"0\n");
            }
            else {
                dfs(0, 0);
                sb.append("#" + tc + " " + result + "\n");
            }
 
        } // tc 종료
 
        // 출력
        System.out.println(sb);
 
    } // main 종료
 
    // dfs 수행
    static void dfs(int level, int cnt) {
 
        // 가지치기
        if (cnt >= result)
            return;
 
        // 종료 조건
        if (level == D) {
 
            if (check()) {
                result = cnt;
            }
 
            return;
        }
 
        // 미선택
        dfs(level + 1, cnt);
 
        // 원복 배열
        int temp[] = map[level].clone();
 
        // A 선택
        for (int i = 0; i < W; i++) {
            map[level][i] = 0;
        }
 
        // 다음 행 이동
        dfs(level + 1, cnt + 1);
 
        // B 선택
        for (int i = 0; i < W; i++) {
            map[level][i] = 1;
        }
 
        // 다음 행 이동
        dfs(level + 1, cnt + 1);
 
        // 백트래킹
        map[level] = temp;
 
    } // dfs 종료
 
    private static boolean check() {
        // 모든 열(W)을 검사
        for (int c = 0; c < W; c++) {
            boolean valid = false;
            int count = 1; // 연속된 개수 (자기 자신 포함 1부터 시작)
 
            for (int r = 1; r < D; r++) {
                if (map[r][c] == map[r - 1][c]) {
                    count++;
                } else {
                    count = 1;
                }
 
                if (count >= K) {
                    valid = true;
                    break;
                }
            }
 
            // 단 한 열이라도 기준을 충족하지 못하면 바로 false
            if (!valid)
                return false;
        }
        return true;
    } // check 종료
 
}

카테고리:

업데이트:

참고