[SWEA] 2112번: ［모의 SW 역량테스트］ 보호 필름 (Unrated) - C++ 풀이

DFS

문제

문제 링크

풀이

핵심 알고리즘

DFS

• 시간 복잡도: O(3^D × D × W) — D: 행 수(≤13), W: 열 수(≤20). 가지치기로 실제 탐색은 이론치보다 훨씬 작음

핵심 아이디어

각 행마다 “그대로 두기 / 0으로 전체 도포 / 1로 전체 도포” 세 선택지를 DFS로 전수 탐색한다. 두 가지 가지치기 — 현재 처리 횟수가 최솟값 이상이거나, K를 초과한 경우 — 로 탐색 공간을 대폭 줄인다. 모든 행 처리 후 test()가 모든 열의 합격 여부를 판정하며, 최솟값을 갱신한다.

① 합격 조건 검사 (test)

각 열을 위에서 아래로 순회하며 동일 값의 최대 연속 길이를 세고, K 미만이면 즉시 false를 반환한다. test()는 DFS가 모든 행을 결정한 후에만 호출되므로, 탐색 완료 시점의 완성된 필름 상태를 검증하는 역할이다. 여기서 false가 반환되면 현재 DFS 경로는 폐기된다.

bool test() {
	for (int col = 0; col < W; col++) {
		int type = map[0][col];
		int cnt = 1;
		for (int i = 1; i < D; i++) {
			if (type == map[i][col]) {
				cnt++;
				if (cnt >= K) break;
			} else {
				type = map[i][col];
				cnt = 1;
			}
		}
		if (cnt < K) return false;
	}
	return true;
}

② DFS 가지치기 전략

ans <= cnt는 이미 더 적은 횟수로 합격한 경로가 있으면 조기 종료한다. cnt > K는 K행을 전부 같은 값으로 채우면 반드시 합격하므로 그 이상의 탐색이 무의미하다는 상한 가지치기다. 두 조건만으로 실제 탐색 트리는 이론적 3^D보다 훨씬 작아지며, 이것이 1089ms라는 비교적 긴 시간의 원인이기도 하다 — 가지치기 없이는 불가능한 문제다.

void dfs(int& ans, int idx, int cnt) {
	if (ans <= cnt || cnt > K) return;
	if (idx == D) {
		if (test()) {
			if (ans > cnt)
				ans = cnt;
		}
		return;
	}

③ 행 선택 및 원본 복원

현재 행을 처리하지 않는 경우를 먼저 탐색한 뒤, 0과 1로 전체 도포하는 경우를 순서대로 시도한다. 도포 후 DFS가 끝나면 반드시 map[idx] = copy_map[idx]로 원본을 복원해야 다른 경로의 탐색이 정확하다. answer = K로 초기화해 “K행 이하” 범위만 탐색하도록 상한을 고정하는 점도 주목할 것. 참고로 그 앞의 int answer = 21e8;은 바로 덮어쓰이는 dead code다.

dfs(ans, idx + 1, cnt);

for (int a : {1, 0}) {
	for (int w = 0; w < W; w++) map[idx][w] = a;
	dfs(ans, idx + 1, cnt + 1);
}
map[idx] = copy_map[idx];

---

성능

• 메모리 : 5976 KB

• 시간 : 1089 ms

코드 (C++)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int D, W, K;
vector<vector<int>> map(21, vector<int>(21, 0));
vector<vector<int>> copy_map(21, vector<int>(21, 0));

bool test() {
	for (int col = 0; col < W; col++) {
		int type = map[0][col];
		int cnt = 1;
		for (int i = 1; i < D; i++)
		{
			if (type == map[i][col]) {
				cnt++;
				if (cnt >= K)
					break;
			}
			else {
				type = map[i][col];
				cnt = 1;
			}
		}
		if (cnt < K)
			return false;
	}
	return true;
}

void dfs(int& ans, int idx, int cnt) {
	if (ans <= cnt || cnt > K) return;
	

	// 검사
	if (idx == D) {
		if (test()) {
			if (ans > cnt)
				ans = cnt;
		}
		return;
	}
	
	dfs(ans, idx+1, cnt);

	for (int a : {1, 0}) {
		for (int w = 0; w < W; w++) map[idx][w] = a;

		dfs(ans, idx + 1, cnt + 1);
	}
	map[idx] = copy_map[idx];
}

void solve() {
	//freopen("test.txt", "r", stdin);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++)
	{
		int answer = 21e8;
		cin >> D >> W >> K;
		for (int d = 0; d < D; d++) {
			for (int w = 0; w < W; w++) {
				cin >> map[d][w];
				copy_map[d][w] = map[d][w];
			}
		}
		
		answer = K;
		dfs(answer, 0, 0);

		cout << "#" << tc << " " << answer << "\n";
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	solve();
}

---