[Unsolved][JAVA] SWEA 2112 보호 필름

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

SW Expert Academy

 

1. 서론

 

모의 SW 역량테스트답게 쉽지 않은 문제였다. 어떻게 해야겠다는 것은 알겠으나 구현을 못하겠는,,, 맨날 있는 그런 가슴 아픈 상황 발생...

 

2. 문제 풀이

 

DxW 크기의 2차원 배열이 있다. 이때 동일한 특성의 셀들이 열에서 k개 이상 연속적으로 있어야 한다. 이를 성능검사라고 칭한다. 성능검사를 통과하기 위해서 한 행 전체를 0 혹은 1로 바꾸는 작업을 한다. 이때 이 작업을 최소로 해서 성능검사를 통과하는 최소 작업 횟수를 구하는 것이 문제이다.

 

나는 성능검사하는 함수와 부분집합을 이용한 백트래킹을 하는 함수를 만들어서 문제를 풀려고 했다.

부분집합으로 바꿀 행을 하나씩 뽑아서 거기에 0을 넣고 재귀, 1을 넣고 재귀, 아무것도 넣지 않고 재귀를 해서 d개가 선택되면 성능검사를 해서 몇 번 행을 바꿨는지를 Math.min함수를 사용해서 답을 구하려고 했다.

 

물론 이 방법이 논리적으로 틀린 것은 아니다. 근데 내가 구현을 하지 못했다. (아직도,, 재귀가 어려움) 내 논리를 정확히 구현한 코드를 결국에는 참고해서 풀게 되었다.

 

그런데 시간초과가 나서 보니까 성능 검사해주는 함수에서 한 바퀴를 다 돌고 true, false를 return 해줬는데 중간에 값 안 나오면 바로 return 해줬더니 시간이 반토막 났다.

 

그리고 부분집합말고 조합을 부분집합처럼 각각 0번부터 d번까지 돌리면서 바꿀 행을 뽑아서 코드를 돌리면 또 시간이 반토막 나게 된다. 왜냐하면 작은 수부터 돌리고 가장 먼저 성능검사에 통과하면 그 뒷부분은 실행시간도 큰데 안 돌려도 되기 때문이다.

 

3. 코드 설명

 

1) 부분집합 버전

 

import java.io.*;
import java.util.*;

public class Solution {
	
	static int ans, d, w, k;
	static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int t = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int q = 1; q <= t; q++) {
        	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]; //보호필름 정보
        	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());
        	}
        	
        	ans = Integer.MAX_VALUE;
        	subset(0, 0);
        	sb.append("#" + q + " " + ans + "\n");
        	
        }
        bw.write(sb.toString());
        bw.close(); br.close();
    }
    
    public static boolean check() { //보호 필름 성능 검사
    	int cnt = 0;
    	for (int i = 0; i < w; i++) {
    		int t = 1, ck = map[0][i];
    		for (int j = 1; j < d; j++) {
    			if (map[j][i] == ck)
    				t++;
    			if (t == k) {//k개 연속인 경우
    				cnt++;
    				break;
    			}
    			if (map[j][i] != ck) {
    				t = 1;
    				ck = map[j][i];
    			}
    		}
            if (t < k) return false; //k보다 작으면 의미 x
    	}
    	
    	if (cnt == w) return true;
    	return false;
    }
    
    public static void subset(int idx, int cnt) {//부분집합을 이용한 일종의 백트래킹
    	if (idx == d) {
    		if (check())//성능 검사 통과한 경우
        		ans = Math.min(ans, cnt); //가장 최소 투입 체크
    		return;
    	}
    	
    	subset(idx + 1, cnt);//약물을 투입하지 않은 경우
    	
    	int[] tmp = map[idx];
    	int[] layer = new int[w];
    	
    	map[idx] = layer;// 특성 A를 투입한 경우
    	subset(idx + 1, cnt + 1);
    	
    	Arrays.fill(layer, 1);//특성 B를 투입한 경우
    	map[idx] = layer;
    	subset(idx + 1, cnt + 1);
    	
    	map[idx] = tmp; //원래대로 값을 되돌림
    }
}

 

성능검사에서 k개보다 같더나 큰 것만 맞고 나머지는 아니기 때문에 발견하면 바로 false로 return 해준다.

부분집합 부분에서 약물을 투입하지 않은 경우는 세지 않으므로 cnt를 추가하지 않고 뽑았다는 의미의 idx만 더해준다.

tmp에 원래의 값을 임시로 담아주고 map[idx], 즉 행값을 전부 0 혹은 1로 대치해준다.

그렇게 전부 뽑은 후(idx == d) 최솟값을 구한다.

 

 

2) 부분집합을 조합으로 구한 버전

 

import java.io.*;
import java.util.*;


public class Solution{
	
	static int ans, d, w, k;
	static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int t = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int q = 1; q <= t; q++) {
        	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]; //보호필름 정보
        	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());
        	}
        	
        	ans = Integer.MAX_VALUE;
        	for (int i = 0; i <= d; i++) {//작은 수부터 검사
        		comb(0, 0, i);
        		if (ans < Integer.MAX_VALUE) //가장 작은 경우가 답
        			break;
        	}
        		
        	sb.append("#" + q + " " + ans + "\n");
        	
        }
        bw.write(sb.toString());
        bw.close(); br.close();
    }
    
    public static boolean check() { //보호 필름 성능 검사
    	int cnt = 0;
    	for (int i = 0; i < w; i++) {
    		int t = 1, ck = map[0][i];
    		for (int j = 1; j < d; j++) {
    			if (map[j][i] == ck)
    				t++;
    			if (t == k) {//k개 연속인 경우
    				cnt++;
    				break;
    			}
    			if (map[j][i] != ck) {
    				t = 1;
    				ck = map[j][i];
    			}
    		}
    		if (t < k) return false; //k보다 작으면 의미 x
    	}
    	
    	if (cnt == w) return true;
    	return false;
    }
    
    public static void comb(int idx, int cnt, int r) {//부분집합을 이용한 일종의 백트래킹
    	if (cnt == r) { //r개 선택한 경우
    		if (check())//성능 검사 통과한 경우
        		ans = Math.min(ans, cnt); //가장 최소 투입 체크
    		return;
    	}
    	if (idx == d) return; //전부 선택된 경우
        
    	comb(idx + 1, cnt, r);//약물을 투입하지 않은 경우
    	
    	int[] tmp = map[idx];
    	int[] layer = new int[w];
    	
    	map[idx] = layer;// 특성 A를 투입한 경우
    	comb(idx + 1, cnt + 1, r);
    	
    	Arrays.fill(layer, 1);//특성 B를 투입한 경우
    	map[idx] = layer;
    	comb(idx + 1, cnt + 1, r);
    	
    	map[idx] = tmp; //원래대로 값을 되돌림
    }
}

 

부분집합으로 통채로 구하는 로직을 0~d개씩 뽑는 단위로 쪼개서 뽑은 것과 같다. 대신 빨리 구하면 빨리 멈춰서 시간이 적게 걸리게 된다.

 

진짜 코드는 이렇게 짜야한다는 것을 많이 느끼게 된다... 대단.