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

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

SW Expert Academy

생각

행을 기준으로 약품을 주입한다, A를 주입한다, B를 주입한다 세가지 경우가 존재합니다. D개의 row에 이러한 세가지 상태가 적용되는 모든 경우를 탐색해야 합니다.

 

부분집합 개념을 사용하여 위의 세가지 상태를 재귀함수로 구현했습니다. 이때 map 상태배열을 직접적으로 수정하기 때문에 세개의 재귀 호출 다음 map 상태배열값을 원복해주는 작업이 필요합니다.

 

그 다음 base case에서는 내가 찾은 최소약품주입횟수가 이전에 찾은 답보다 크거나 같을땐 더 이상 탐색할 필요가 없기 때문에 바로 return 시켜줍니다. (유망하지 않음)
다음 base case는 row가 마지막일때입니다. 이때 모든 열이 최소 K개만큼 연결되있는지를 확인한다음 최소가 되는 약품주입횟수를 찾아줍니다.

 

모든 열이 K개 만큼 연결되있는지를 체크하는 함수는 열을 기준으로 row의 인덱스를 반복해서 검사합니다.
cnt 변수는 연속하는 원소를 카운트해주는 값입니다.
이때 현재값과 다음값을 비교하여 같지 않다면 cnt를 1로 초기화해줍니다.
만약 연속한다면 cnt를 1씩 증가시켜주고 cnt 가 K개 이상이라면 break를 걸어 다음 열을 검사하도록 넘어갑니다.
하나의 열에 대한 검사가 끝난 뒤 cnt가 K개 미만이라면 return false 를 합니다.

 

(참고) 두번째 풀이는 statusByRow라는 리스트를 사용하여 각 행에 대한 상태값을 저장시켜줬습니다. (statusByRow[i] : i번째 행의 상태값, -1 : 약품처리안함, 0 : A 약품처리, 1 : B 약품처리)
이 방식을 사용하면 상태배열 map의 값을 바꾸지 않고도 dfs로 처리 할 수 있습니다. 약품을 처리하면 해당 row가 모두 동일 값으로 바뀌는 상태이기 때문입니다. 

Java Code 1 - 부분집합 풀이

package com.java.algorithm;

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

public class SWEA_2112_보호필름_부분집합 {
	static int D,W,K;
	static int[][] map;
	static int[][] copymap;
	static int ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			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];
			copymap = 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());
					copymap[i][j] = map[i][j];
					
				}
			}
			ans = Integer.MAX_VALUE;
			solve2(0,0);
			sb.append("#").append(t).append(" ").append(ans).append("\n");
		}
		System.out.println(sb);
	}
	
	
	//행을 선택하는 부분집합
	private static void solve2(int row, int cnt) {
		if(cnt >= ans) return;
		if(row == D) {
			if(isContinue2()) {
				ans = Math.min(ans, cnt);
			}
			return;
		}
		//1.아무것도 투약 안함
		solve2(row+1, cnt);
		
		//2.A투약
		for (int i = 0; i < W; i++) {
			map[row][i] = 0;
		}
		solve2(row+1, cnt+1);
		
		//3.B투약
		for (int i = 0; i < W; i++) {
			map[row][i] = 1;
		}
		solve2(row+1, cnt+1);
		
		//상태배열 원복
		for (int i = 0; i < W; i++) {
			map[row][i] = copymap[row][i];
		}
		
	}
	
	
	private static boolean isContinue2() {
		int now,next;
		for (int x = 0; x < W; x++) {
			int cnt = 1; //연속하는원소 카운트
			for (int y = 0; y < D-1; y++) {
				now = map[y][x];
				next = map[y+1][x];
				if(now == next) {
					cnt++;
					if(cnt >= K) break;
					
				}
				else {
					cnt=1;//초기화되서 다시 카운트 시작
				}
				
			}
			if(cnt < K) return false;

		}
		
		return true;
	}
	

}

 

Java Code 2 - row 상태 리스트를 사용한 풀이

package com.java.algorithm;

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

public class SWEA_2112_보호필름 {
	static int D,W,K;
	static int[][] map;
	static int[] statusByRow; // 각 row별 약품 투약 상태 리스트 (-1 : 투여안함,  0: a 투여,  1 : b 투여)
	static int ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			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];
			statusByRow = new int[D];
			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;
			dfs(0,0);
			sb.append("#").append(t).append(" ").append(ans).append("\n");
		}
		System.out.println(sb);
	}
	
	private static void dfs(int row, int cnt) {
		//내가 구한 최소값보다 더 크면 더이상 탐색하지 않음
		if(cnt >= ans) return;
		//맨 마지막에 도달하면 모든 열 연속되있는지 확인하고 답 찾기
		if(row == D) {
			if(isContinue()) {
				ans = Math.min(ans, cnt);
			}
			return;
		}
		
		for (int i = -1; i < 2; i++) {
			statusByRow[row] = i;
			if(i == -1) {
				dfs(row+1, cnt);
			}else {
				dfs(row+1, cnt+1);
			}
		}
	}
	
	
	private static boolean isContinue() {
		int now,next;
		for (int x = 0; x < W; x++) {
			int cnt = 1; //연속하는원소 카운트
			for (int y = 0; y < D-1; y++) {
				now = statusByRow[y] == -1 ? map[y][x] : statusByRow[y];
				next = statusByRow[y+1] == -1 ? map[y+1][x] : statusByRow[y+1];
				if(now == next) {
					cnt++;
					if(cnt >= K) break;
					
				}
				else {
					cnt=1;//초기화되서 다시 카운트 시작
				}
				
			}
			if(cnt < K) return false;

		}
		
		return true;
	}
	
	

}