[SWEA] 2112. [모의 SW 역량테스트] 보호 필름
📝 풀이 과정
부분 집합을 이용해서 약물을 투여할 행을 선택하는 것이 키포인트
-
부분 집합을 이용해서 약물 투여 대상을 정한다.
해당 행 선택, 선택하지 않음 -
선택된 행들을 dfs를 통해 탐색한다.
void drug(boolean[] isSelected, int idx, int cnt) -
선택된 idx인 경우 0(A)과 1(B)으로 채워서 dfs 탐색 진행
아닌 경우 약물 투여하지 않고, 다음 idx로 탐색 진행 -
탐색이 끝나면 유효성 검사를 한다.
검사에 통과하면 결과 값을 최솟값으로 갱신한다. -
보호필름 배열을 초기화 하고, 위 과정을 반복한다.
👩🏻💻 제출 코드
📍 1차 코드 : DFS 탐색
메모리 : 117,964 kb
실행 시간 : 808 ms
-
DFS(깊이 우선 탐색)를 사용하여 각 행마다 약물을 투여하거나 투여하지 않는 모든 경우를 재귀적으로 탐색한다.
-
탐색을 시작하기 전에 초기 검사 없이 바로 DFS를 진행한다.
-
탐색 후 배열을 복사하여 필름 상태를 원래대로 복원한다.
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 D, W, K;
static int[][] film;
static int drugCnt;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int t = 1; t <= T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
D = Integer.parseInt(st.nextToken()); // 보호필름의 두께
W = Integer.parseInt(st.nextToken()); // 보호필름의 가로 크기
K = Integer.parseInt(st.nextToken()); // 합격 기준
drugCnt = Integer.MAX_VALUE;
film = new int[D][W];
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());
}
}
drug(0, 0);
System.out.println("#" + t + " " + drugCnt);
}
}
// idx: 약물투여 대상 행의 위치, cnt: 약물 투여 횟수
private static void drug(int idx, int cnt) {
if(test()) { // 검사에 통과한 경우, 최소 투여 횟수로 설정
drugCnt = Math.min(cnt, drugCnt);
return;
}
if(cnt > drugCnt) return; // 최소 투여 횟수보다 많은 경우 return
if(idx == D) return; // 모든 행을 탐색한 경우 return
int[] memory = new int[W];
// 약물 투여하지 않고 검사하기
for(int i = 0; i < W; i++) {
memory[i] = film[idx][i];
}
drug(idx + 1, cnt);
// idx행 약품 A 투여하고 검사하기
for(int i = 0; i < W; i++) {
film[idx][i] = 0;
}
drug(idx + 1, cnt + 1);
// idx행 약품 B 투여하고 검사하기
for(int i = 0; i < W; i++) {
film[idx][i] = 1;
}
drug(idx + 1, cnt + 1);
// idx행 원상복구
film[idx] = Arrays.copyOf(memory, memory.length);
}
private static boolean test() {
for(int i = 0; i < W; i++) {
int count = 1;
boolean pass = false;
for(int j = 1; j < D; j++) {
if(film[j - 1][i] == film[j][i]) {
count++;
}
else {
count = 1;
}
if(count >= K) {
pass = true;
break;
}
}
if(!pass) return false;
}
return true;
}
}📍 2차 코드 : 부분 집합 탐색
메모리 : 38,180 kb
실행 시간 : 526 ms
-
부분 집합 생성을 통해 선택된 행에 대해서만 약물을 투여하는 방식으로 탐색합니다.
-
탐색 전 먼저 현재 필름 상태로 테스트를 통과할 수 있는지 검사하여, 초기 상태에서 통과 가능하면 탐색을 생략합니다.
-
reset()메서드를 사용해 탐색 후 필름 상태를 복구합니다.
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 D, W, K;
static int[][] film;
static int[][] map;
static boolean[] isSelected;
static int drugCnt;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int t = 1; t <= T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
D = Integer.parseInt(st.nextToken()); // 보호필름의 두께
W = Integer.parseInt(st.nextToken()); // 보호필름의 가로 크기
K = Integer.parseInt(st.nextToken()); // 합격 기준
drugCnt = Integer.MAX_VALUE;
film = new int[D][W];
map = new int[D][W];
isSelected = 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());
map[i][j] = film[i][j];
}
}
if(test()) {
System.out.println("#" + t + " " + 0);
}
else {
subSet(0);
System.out.println("#" + t + " " + drugCnt);
}
}
}
// 부분 집합으로 투여할 행 선택하기
private static void subSet(int idx) {
if(idx == D) {
drug(isSelected, 0, 0);
reset();
return;
}
subSet(idx + 1);
isSelected[idx] = true;
subSet(idx + 1);
isSelected[idx] = false;
}
// idx: 약물투여 대상 행의 위치, cnt: 약물 투여 횟수
private static void drug(boolean[] isSelected, int idx, int cnt) {
if(cnt >= drugCnt) return;
if(idx == D) {
if(test()) {
drugCnt = Math.min(cnt, drugCnt);
}
return;
}
if(isSelected[idx]) {
Arrays.fill(film[idx], 1);
drug(isSelected, idx + 1, cnt + 1);
Arrays.fill(film[idx], 0);
drug(isSelected, idx + 1, cnt + 1);
}
else {
drug(isSelected, idx + 1, cnt);
}
}
private static boolean test() {
for(int i = 0; i < W; i++) {
int count = 1;
boolean pass = false;
for(int j = 1; j < D; j++) {
if(film[j - 1][i] == film[j][i]) {
count++;
}
else {
count = 1;
}
if(count >= K) {
pass = true;
break;
}
}
if(!pass) return false;
}
return true;
}
// 보호필름 초기화 하기
private static void reset() {
for(int i = 0; i < D; i++) {
for(int j = 0; j < W; j++) {
film[i][j] = map[i][j];
}
}
}
}
항상 궁금해하기