[SWEA] 2112. [모의 SW 역량테스트] 보호 필름 - Java

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

SW Expert Academy

---

1. 문제 요약

보호 필름의 두께D, 가로W, 합격기준K와 보호 필름을 입력받는다.

각 열마다 동일한 특성(A또는 B)이 K개 이상 연속될 경우 조건을 만족하며,

각 행마다 모두 같은 특성으로 바꾸는 '약품 투입'을 시행할 수 있다.

출력은 이 '약품 투입'의 최소 횟수를 출력해야 한다. 따라서 약품 투입을 하지 않고 조건을 만족하는 경우도 있는데,

이와 같은 경우는 0을 출력하면 된다.

( 3<=D<=13)

2. 풀이

1차 - 22.10.17

백트래킹 문제이다.

tmp[][] 배열을 만들어서 map과 동일한 값을 넣어주고, 여기에 직접 A를 넣고 B를 넣고 원복해주는 것을 반복한다.

dfs에서 다음을 반복한다. 파라미터로 색칠하고 가는 횟수와 층수를 넘겨준다.

1. 약품 투입 안하고 갔을 경우 (색칠 X)

2. 약품 투입 A로 하고 갔을 경우 (A로 색칠)

3. 약품 투입 B로 하고 갔을 경우 (B로 색칠)

4. 다 해봤으니 원복 (색칠한거 원복)

그리고 기저조건에서

D-1층 전부 다 봤을 경우, 조건을 만족하면 횟수 min을 갱신해준다.

조건은

각 열에 대하여 현재 층의 특성이 이전 층의 특성과 동일하다면 cnt를 늘려주고,

다르다면 cnt=1로 다시 초기화해준다.

cnt==K가 되면 flag를 true로 바꿔주고,

만약 D-1층까지 다 봤음에도 flag가 여전히 false라면, 그것은 조건을 만족하지 않는 경우이므로

더 볼 필요가 없으니 false를 리턴해준다.

 

----

2차 - 22.11.15

부분집합(백트래킹) 문제이다.

10시부터 풀어서 2시에 끝났다. dfs에는 문제가 없었고 정답 판별하는 함수에서 문제가 있었다.

내가 놓친 부분은 K=1이 될 수 있다는 것이었다.

check() 함수에서 카운트를 1로 초기화하고 이전값과 현재값이 같으면 1을 늘려준 다음

cnt개수가 K와 같은지 봤는데

이렇게하면 이전값과 현재값이 같아서 2가 되었는데 K는 1인 경우가 발생할 수 있다.

이 경우가 무시된다. 그래서 테스트케이스 49/50 개의 연속이었다.

K가 1일 때는 무조건 true를 리턴해야 한다. 이걸 check()함수 맨 첫줄에 추가하니까 통과했다.

 

* 선택안하고 가는 dfs부터 해주는게 빠르다.

선택안하는 dfs 먼저했을 때

선택하는 dfs 먼저했을 때

 

 

3. 코드

1차 (솔루션 참고해서 품) 22.10.17

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

public class SW_2112_보호필름 {

	static int W, D, K, ans;
	static int[][] map, tmp;
	
	public static void main(String[] args) throws Exception {
		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());
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[D][W];
			tmp = new int[D][W];
			
			for (int i=0; i < D; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j<W; j++) {
					int num = Integer.parseInt(st.nextToken());
					map[i][j] = tmp[i][j] = num;
				}
			}
			
			ans = Integer.MAX_VALUE;
			if (check()) ans=0;
			else dfs(0,0);
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void dfs(int floor, int cnt) { //cnt:줄 색깔 바꾼 횟수
		if (cnt >= ans) return;
		
		if (floor == D) {
			if (check()) {
				ans = Math.min(ans, cnt); //제일 적게 바꿔준 횟수
			}
			return;
		}
		
		dfs(floor+1, cnt); //색칠 안함
		
		for (int i=0; i < W; i++) {
			tmp[floor][i]=0; //A로 색칠
		}
		dfs(floor+1, cnt+1);
		
		for (int i=0; i<W; i++) {
			tmp[floor][i]=1; //B로 색칠
		}
		dfs(floor+1, cnt+1);
		
		for (int i=0; i<W; i++) {
			tmp[floor][i] = map[floor][i]; //원복
		}
	}
	
	static boolean check() {
		for (int x=0; x<W; x++) {
			boolean isOk = false;
			int cnt=1;
			for (int y=1; y<D; y++) {
				if (tmp[y][x] == tmp[y-1][x]) cnt++;
				else cnt=1;
				if (cnt == K) {
					isOk = true;
					break;
				}
			}
			if (!isOk) return false;
		}
		return true;
	}
}

2차 (솔루션 안봄) - 22.11.15

package a22_11_14;

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

public class SW_2112_보호필름 {

	static int D,W,K, ans;
	static int[][] map, cmap;
	
	public static void main(String[] args) throws Exception {
		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());
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[D][W];
			cmap = 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());
					cmap[i][j] = map[i][j];
				}
			} //입력 끝
			
			ans = Integer.MAX_VALUE;
			subset(0, 0);
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void subset(int cnt, int used) {
		if (ans < used) return;
		if (cnt == D) {
			if (check() == true) {
				ans = Math.min(ans, used);
			}
			return;
		}

		subset(cnt+1, used);
		A(cnt);
		subset(cnt+1, used+1);
		B(cnt);
		subset(cnt+1, used+1);
		restore(cnt);
	}
	
	static boolean check() {
		if (K == 1) return true; //내가 놓친 부분 : K가 1이될 수 있다
		
		for (int i=0; i<W; i++) {
			
			boolean isCan = false;
			int cnt = 1;
			int before=cmap[0][i]; //맨 첫줄
			
			for (int j=1; j<D; j++) {
				int now = cmap[j][i];
				if (before==now) {
					cnt++;
					if (cnt==K) {
						isCan = true;
						break;
					}
				} else {
					cnt = 1;
				}
				before = now;
			}
			if (isCan != true) return false;
		}
		return true;
	}
	
	static void A(int cnt) {
		for (int i=0; i<W; i++) {
			cmap[cnt][i] = 0;
		}
	}
	static void B(int cnt) {
		for (int i=0; i<W; i++) {
			cmap[cnt][i] = 1;
		}
	}
	
	static void restore(int cnt) {
		for (int i=0; i<W; i++) {
			cmap[cnt][i] = map[cnt][i];
		}
	}
}

 

4. 사담

check()함수가 오히려 dfs보다 어려웠던 문제였다.

이전에 솔루션보고 풀었던 문제인데 솔루션 없이 다시풀려고 하니까 막막했다.

아직 갈길이 멀다는걸 또 깨닫는다. 부지런히 하자