2112번 : 보호 필름 [Java]

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

SW Expert Academy

해결 방식 고민

3진 트리를 사용하는 방법과 조합을 사용하는 방법 2가지가 있다.

다들 3진트리를 많이 사용했던데,,

3진 트리를 사용한 코드가 훨씬 깔끔했지만 개인적으로는 조합을 사용해서 푼 게 더 이해가 잘됐다.

 

해결 방안 _1 : 3진트리

1. dfs를 사용

1-1. 아무것도 투입하지 않은 경우

1-2. A를 투입한 경우

1-3. B를 투입할 경우

2. 모든 경우를 확인하면 배열을 돌려놓는다.

 

전체 코드 _1

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

public class Solution {
	static StringTokenizer st;
	static int D, W, K;
	static int[][] map, copy;
	static int ans;

	public static void main(String[] args) throws IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(input.readLine());
		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(input.readLine(), " ");
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[D][W];
			copy = new int[D][W];

			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(input.readLine(), " ");
				for (int j = 0; j < W; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					copy[i][j] = map[i][j];
				}
			}

			if (K == 1 || isPossible()) { // 바로 통과 -> 다음 테케로
				System.out.println("#" + tc + " " + 0);
				continue;
			}

			ans = 987645321;
			dfs(0, 0);
			System.out.println("#" + tc + " " + ans);
		}
	}

	private static void dfs(int row, int cnt) {
		if (cnt >= ans) // 크거나 같으면 더 볼 필요 없다.
			return;
		if (row == D) {
			// 마지막 줄까지 바꿨다면 검사하자
			if (isPossible())
				ans = Math.min(ans, cnt); // 최솟값 저장
			return;
		}

		// 아무것도 투입하지 않는 경우
		dfs(row + 1, cnt);

		// A약품을 투입하는 경우 -> 0넣기
		for (int i = 0; i < W; i++) {
			map[row][i] = 0;
		}
		dfs(row + 1, cnt + 1);

		// B약품을 투입하는 경우 -> 1넣기
		for (int i = 0; i < W; i++) {
			map[row][i] = 1;
		}
		dfs(row + 1, cnt + 1);

		// 되돌리기
		for (int i = 0; i < W; i++) {
			map[row][i] = copy[row][i];
		}
	}

	private static boolean isPossible() {
		for (int j = 0; j < W; j++) {
			int cnt = 0;
			int cur = map[0][j];
			boolean ck = false;
			for (int i = 0; i < D; i++) {
				if (map[i][j] == cur)
					cnt++;
				else {
					cur = map[i][j];
					cnt = 1;
				}
				if (cnt == K) {
					ck = true;
					break;
				}
			}
			if (!ck)
				return false;
		}
		return true;
	}
}

해결 방안 _2 : 조합 사용

1. 투입 횟수에 따라 투입될 행을 정한다.

2. 선택된 행마다 약품의 종류를 정한다.

3. 약품을 넣고 검사한 뒤 배열을 돌려놓는다.

 

전체 코드 _2

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

public class Solution {
	static StringTokenizer st;
	static int D, W, K;
	static int[][] map, copy;
	static int[] numbers, ab;
	static int ans;

	public static void main(String[] args) throws IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(input.readLine());
		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(input.readLine(), " ");
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[D][W];
			copy = new int[D][W];

			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(input.readLine(), " ");
				for (int j = 0; j < W; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					copy[i][j] = map[i][j];
				}
			}

			if (K == 1 || isPossible()) { // 바로 통과 -> 다음 테케로
				System.out.println("#" + tc + " " + 0);
				continue;
			}

			ans = 987645321;
			for (int i = 1; i <= D; i++) { // 투입 횟수
				numbers = new int[i];
				selectR(0, 0, i);
			}
			System.out.println("#" + tc + " " + ans);
		}
	}

	private static void selectR(int start, int idx, int cnt) { // cnt : 바꿀 행의 수

		if (idx == cnt) {
			if (ans > cnt) { // 답보다 적은 경우만 확인

				// 행마다 약품 종류 정하기
				ab = new int[cnt];
				choice(0, cnt);

				for (int i = 0; i < D; i++) { // 돌려놓기
					for (int j = 0; j < W; j++) {
						map[i][j] = copy[i][j];
					}
				}
			}
			return;
		}
		for (int i = start; i < D; i++) {
			// 투입될 곳을 정한다 -> 1~D중 cnt개 선택
			numbers[idx] = i;
			selectR(i + 1, idx + 1, cnt);
		}

	}

	private static void choice(int idx, int cnt) {
		if (idx == cnt) {
			// 해당하는 약물을 넣고 검사
			for (int i = 0; i < cnt; i++) {
				for (int j = 0; j < W; j++) {
					map[numbers[i]][j] = ab[i];
				}
			}
			if (isPossible())
				ans = cnt;

			return;
		}
		for (int i = 0; i < 2; i++) {
			// 투입될 약품을 정한다 -> a, b 중 선택
			ab[idx] = i;
			choice(idx + 1, cnt);
		}

	}

	private static boolean isPossible() {
		for (int j = 0; j < W; j++) {
			int cnt = 0;
			int cur = map[0][j];
			boolean ck = false;
			for (int i = 0; i < D; i++) {
				if (map[i][j] == cur)
					cnt++;
				else {
					cur = map[i][j];
					cnt = 1;
				}
				if (cnt == K) {
					ck = true;
					break;
				}
			}
			if (!ck)
				return false;
		}
		return true;
	}
}