[삼성 SW Expert Academy] [모의 SW 역량테스트] 보호 필름 [Java]

| Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

---

| Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

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

SW Expert Academy

---

| 풀이

1. Step : 최소 약품 사용 개수 구하기 위해서는 어차피 완탐을 해야한다.  - DFS
2. Step : 맨 위 행을 기준으로 내려가면서 1) 아무것도 바꾸지 않는다. 2) A로 변경하기 3) B로 변경하기
3.  

 4. Step : O(3^13)

---

| 어려웠던 점

틀린 방법 - 부분집합 사용 - 시간 복잡도를 좀더 세심하게 생각하고 문제를 풀어야 한다.

1. Step 두께 최대 13개의 부분집합을 모두 구했다. (  O(2^13) )
2. Step 각 집합마다 ==> A로 덮어쓸지 B로 덮어 쓸지에 대한 부분집합을 또 한번 구했다. ( O(2^13) ) 
3. Step 그 집합에서 조건이 충족되는지를 검사했고, 그 때의 최소값을 구하고자 했다.
4. 총 시간복잡도 최대로 잡으면 O(2^26) 되는 것 같다. - 아니라면, 댓글로 남겨주시면 감사하겠습니다.
5. 36/50개 에서 fail 

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[][] film, film_clone; // row : D , column : W
    static int D, W, K;
    static boolean[] drug,color; // 약품
    static int Tc, answer ;
    static boolean find;
    static int[] sel;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
        Tc = Integer.parseInt(st.nextToken()); // column
 
        for (int tc = 1; tc <= Tc; tc++) {
 
            st = new StringTokenizer(br.readLine(), " ");
            D = Integer.parseInt(st.nextToken()); // 행
            W = Integer.parseInt(st.nextToken()); // 열
            K = Integer.parseInt(st.nextToken()); // 합격 기준
 
            film = new int[D][W];
            film_clone = new int[D][W];
            drug = new boolean[D];
            find = false;
            answer = Integer.MAX_VALUE;
            sel = new int[D];
            color = new boolean[D]; // 약품 색깔
            for (int i = 0; i < D; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < W; j++) {
                    film[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            copy();
             
            find = check();
            // 1. dfs 를 통해 각 행하나씩 바꿔가면서
            if (!find) {
                dfs(0, 0);
            }
            else {
                answer = 0;
            }
            // 2. 조건 충족하는지 체크하기.
 
            System.out.println("#" + tc + " "+answer);
        }
 
    }
    private static void copy() {
         
        for( int i=0; i<D; i++) {
            for( int j=0; j<W; j++) {
                film_clone[i][j] = film[i][j];
            }
        }
    }
    private static void change(int depth) {
         
         
        if ( depth == sel.length) {
            for( int i=0; i<sel.length; i++) {
                // true -> 0 으로 채우기
                int c =0 ;
                if( color[ sel[i]] ) {
                    while( true ) {
                        film_clone[ sel[i] ][c++] = 0;
                        if ( c == W) break;
                    }
                }
                // false -> 1 로 채우기
                else if ( !color[sel[i]]) {
                    while( true ) {
                        film_clone[ sel[i] ][c++] = 1;
                        if ( c == W) break;
                    }
                }
                 
            }
            if( check() ) {
                answer = Math.min(answer, sel.length);
            }
            copy();
            return;
        }
         
         
        color [ sel[depth] ] = true;
        change(depth+1);
        color [ sel[depth] ] = false;
        change(depth+1);
         
    }
 
    private static void dfs(int select, int depth) {
 
        if (depth == D) {
            int idx = 0;
            // drug[i]에 따라서, film 행의 색 복구
            sel = new int[select];
            for (int i = 0; i < D; i++) {
                if (drug[i]) {
                    // drug[i]에 따라서, film 행의 색 바꾸기
                    sel[idx++] = i;
                }
            }
            change(0);
 
            return;
        }
 
        drug[depth] = true;
        dfs(select + 1, depth + 1);
        drug[depth] = false;
        dfs(select, depth + 1);
    }
 
    // 연속 3개 인거 체크
    private static boolean check() {
        int before;
        int max;
        // D : 행, W : 열
        for (int i = 0; i < W; i++) {
            int cnt = 1;
            before = film_clone[0][i];
            max = -1;
            for (int j = 1; j < D; j++) {
 
                if (film_clone[j][i] == before)
                    cnt++;
                else {
                    before = film_clone[j][i];
                    cnt = 1;
                }
                max = Math.max(max, cnt); // 연속된 개수 최대 개수 측정
                if (max >= K)
                    continue; // K개 이상이면 다음꺼 검사
            }
            if (max < K)
                return false; // 한 열에서 최대 개수가 K가 안되면 실패
        }
         
        return true;
    }
 
}

---

| 코드 - 정답

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

public class 최장경로_2814 {
	
	static int Tc;   // Tc
	static int N, M; // N - 정점의 개수, M - 간선의 개수 
	static ArrayList<Integer>[] start;   
	static int answer; 
	static boolean[] visited ;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		Tc = Integer.parseInt(br.readLine());
		
		for( int tc = 1; tc<=Tc; tc++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken()); // 정점 수 
			M = Integer.parseInt(st.nextToken()); // 간선 수 
			answer =  1; 
			
			start  = new ArrayList[N]; // 각 노드에 연결된 정점들
			visited = new boolean[N];  // 노드 방문 여부 
			
			for( int i=0; i<N; i++) {
				start[i] = new ArrayList<>();
			}
			
			
			// 1. arraylist에 연결된 정점 저장
			for( int i=0; i< M; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int from = Integer.parseInt(st.nextToken()) -1 ;  // 시작 정점
				int to = Integer.parseInt(st.nextToken()) - 1 ; // 도착 정점
				
				start[from].add(to);
				start[to].add(from);
			}
			
			// 2. 연결된 정점 모두 타고 들어가면서, dfs
			for( int Strt=0; Strt< N; Strt++) {
				visited[Strt] = true;
				dfs(Strt, 1, 0);
				visited[Strt] = false;
				
			}
			// 2-1. 
			
			// 3. 가장 depth 긴것,
			
			System.out.println("#"+tc+" "+answer);
		}
	}
	private static void dfs(int startNode, int step, int depth) {
		answer = Math.max( step , answer);
		
		// base rule
		if ( depth == N ) return;
		
		
		// 연결된 노드 타고 들어가자.
		for( int to = 0; to< start[startNode].size(); to++) {
			
			int target = start[startNode].get(to);
			if ( visited[ target ] ) continue; // 방문한 곳이면 가지말고
			
			// 처음 보는 곳이면
			visited[ target ]  = true; // 방문처리하고
			dfs( target, step+1, depth+1); // dfs
			visited[ target ] = false;
			
		}	
	}	
}

---

| 보완할 점

1. 시간 복잡도 계산 하는 습관
2. 다양한 문제 풀어보고, 복습 열심히 !
3. DFS의 다양한 활용법

---