[삼성 SW EA - dfs] 보호필름

Maps를 무작정 조작하려 들기보다는, 출력에 필요한 정보를 dfs로 전달하는 것이 좋다.

아래처럼, 

DFS에 들어갔을 때 -> 현재 상태에 대한 배열을 만들고 -> 함수 인자 값으로 받아온 이전 상태로 현재 상태에 대한 배열을 채워준다. -> 그리고 채워준 현재 상태의 배열로 DFS에 들어간다.

굳이 인자에 들어온 값을 조작하려 들지 말고, 인자로 들어온 이전 값을 활용하여 현재 값을 채운 후 보내주자. 그러면 이것이 백트래킹이 된다.

또한, 삼항 연산자를 쓰니 굉장히 보기 편하다. 반성해야겠다.

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
class Solution {
    static int[][] maps;
    static int[] chemical;
    static int D,W,K, answer;
    static final int DSIZE=13, WSIZE=20;
    
    public static void main(String[] args) throws FileNotFoundException {
        //Scanner sc = new Scanner(System.in);
        Scanner sc = new Scanner(new FileInputStream("C:\\Users\\SeonMi\\Desktop\\JavaTools\\Tools\\workspace\\SamsungGoGo\\sample_input.txt"));
        int T = sc.nextInt();
        for(int t=1;t<=T;t++){
            answer = 999999;
            D = sc.nextInt();
            W = sc.nextInt();
            K = sc.nextInt();
            maps = new int[DSIZE][WSIZE];
            for(int i=0;i<D;i++){
                for(int j=0;j<W;j++){
                    maps[i][j]=sc.nextInt();
                }
            }
            
            for(int ch=0;ch<3;ch++){
                chemical = new int[D];
                int[] maxChemical = new int[W];
                int[] currentMaxChemical = new int[W];
                
                chemical[0] = ch;
                for(int i=0;i<W;i++){
                    maxChemical[i] = 1;
                    currentMaxChemical[i] = 1;
                }
                if(ch==2)
                    dfs(1,0, maxChemical, currentMaxChemical);
                else
                    dfs(1,1, maxChemical, currentMaxChemical);
                
            }
            
            if(answer==999999)
                answer=0;
            
            System.out.println("#"+t+" "+answer);
        }
    }
 
    static void dfs(int curD, int count, int[] prevMaxChemical,int[] prevCurrentChemical) {
        if(count>D) // 약품 처리 횟수가 D를 초과한 경우는 제외 
            return;
 
        if(curD==D){ // 마지막 깊이까지 온 경우
            boolean isSatisfied = true;
            
            for(int w=0 ; w<W; w++){
                if(prevMaxChemical[w]<K){
                    isSatisfied = false;
                    break;
                }
            }
            
            if(isSatisfied)
                answer = Math.min(count, answer);
            return;
        }
        
        
        int[] currentContinue = new int[W]; // 현재 연속하는 보호 필름의 갯수
        int[] currentMax = new int[W]; // 현재 연속하는 보호 필름 최대 갯수
        
        for(int ch=0;ch<3;ch++){// 해당하는 행  약품 처리
            int prev, current;
            chemical[curD] = ch;
 
            for(int i=0;i<W;i++){ // 열 모두 약품처리 해주기 
                prev = chemical[curD-1]==2 ? maps[curD-1][i] : chemical[curD-1];
                current = ch==2 ? maps[curD][i] : chemical[curD];
                
                currentContinue[i] = prev==current? prevCurrentChemical[i]+1 : 1;
                currentMax[i] = currentContinue[i]>prevMaxChemical[i] ? currentContinue[i] : prevMaxChemical[i];
            }
            
            dfs(curD+1, chemical[curD]==2? count:count+1, currentMax, currentContinue);
 
        }
    }
}