[DFS] 가지치기? 메모제이션?

가지치기? 메모제이션?

DFS 풀이에서 시간을 단축시키는 방법은 크게 "가지치기"와 "메모제이션"이 있다.

가지치기

최소값을 구하는 경우, 중간 값이 이전에 구한 최소 값보다 크다면(좋지 않다면) 해당 경우는 가지치기할 수 있다.
그러나 최대값을 구하는 경우에는 중간 값이 이전에 구한 값보다 작음을 판단할 수 없으므로(말그대로 최종 값을 구하기 전의 중간 값이기에) 가지치기를 할 수 없다.

결국 가지치기를 할 수 있는 경우는 최소값을 구하기 위하 DFS를 활용하는 경우에만 사용할 수 있다.

메모제이션

그렇다면 최대값을 구하는 경우는 어떻게 시간을 줄일 수 있을 까? 바로 이때 메모제이션을 활용하면 될 것이다.

또한 리턴값을 적절히 주어 최소값을 구하는 경우에도 메모제이션을 활용할 수 있다.

---

가지치기 예제 문제

색종이 붙이기_백준

source: https://www.acmicpc.net/problem/17136

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> MAP(10, vector<int>(10));

bool checkRectangle(int x, int y, int size, const vector<vector<bool>>& visitedMap) {
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (i < 0 || i >= 10 || j < 0 || j >= 10)
				return false;

			if (MAP[i][j] == 0)
				return false;

			if (visitedMap[i][j])
				return false;
		}
	}

	return true;
}

void checkVisited(int x, int y, int size, vector<vector<bool>>& visitedMap, bool checkType) {
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			visitedMap[i][j] = checkType;
		}
	}
}

// 전역의 최소값(구하고자 하는 답)
const int MAX = 1e9;
int MIN_ANSWER = MAX;

void DFS(int resOnePaper, int usedPaper, vector<vector<bool>>& visitedMap, vector<int>& ResColorPaper, const vector<pair<int, int>>& OnePaper, int idx) {
	// 종료조건
	if (resOnePaper == 0) {
		MIN_ANSWER = min(MIN_ANSWER, usedPaper);
	}

	// 가지치기
	if (usedPaper >= MIN_ANSWER)
		return;


	// 탐색 
	int i = OnePaper[idx].first;
	int j = OnePaper[idx].second;

	if (visitedMap[i][j]) {
		DFS(resOnePaper, usedPaper, visitedMap, ResColorPaper, OnePaper, idx + 1);
		return;
	}

	// 현재 1로 표시된 {x, y} 좌표
	int x = i, y = j;

	// 5x5 색종이를 붙이고 다음 DFS로 전달한다.
	if (ResColorPaper[5] > 0 && checkRectangle(x, y, 5, visitedMap)) {
		// ResColorPaper 감소
		ResColorPaper[5]--;
		// visited 표시
		checkVisited(x, y, 5, visitedMap, true);

		DFS(resOnePaper-25, usedPaper + 1, visitedMap, ResColorPaper, OnePaper, idx+1);

		// visited 복구
		checkVisited(x, y, 5, visitedMap, false);

		// ResColorPaper 증가
		ResColorPaper[5]++;
	}
	// 4x4
	if (ResColorPaper[4] > 0 && checkRectangle(x, y, 4, visitedMap)) {
		ResColorPaper[4]--;
		checkVisited(x, y, 4, visitedMap, true);
		DFS(resOnePaper-16, usedPaper + 1, visitedMap, ResColorPaper, OnePaper, idx + 1);
		checkVisited(x, y, 4, visitedMap, false);
		ResColorPaper[4]++;
	}
	// 3x3
	if (ResColorPaper[3] > 0 && checkRectangle(x, y, 3, visitedMap)) {
		ResColorPaper[3]--;
		checkVisited(x, y, 3, visitedMap, true);
		DFS(resOnePaper - 9, usedPaper + 1, visitedMap, ResColorPaper, OnePaper, idx + 1);
		checkVisited(x, y, 3, visitedMap, false);
		ResColorPaper[3]++;
	}
	// 2x2
	if (ResColorPaper[2] > 0 && checkRectangle(x, y, 2, visitedMap)) {
		ResColorPaper[2]--;
		checkVisited(x, y, 2, visitedMap, true);
		DFS(resOnePaper - 4, usedPaper + 1, visitedMap, ResColorPaper, OnePaper, idx + 1);
		checkVisited(x, y, 2, visitedMap, false);
		ResColorPaper[2]++;
	}
	// 1x1
	if (ResColorPaper[1] > 0) {
		ResColorPaper[1]--;
		visitedMap[i][j] = true;
		DFS(resOnePaper - 1, usedPaper + 1, visitedMap, ResColorPaper, OnePaper, idx + 1);
		visitedMap[i][j] = false;
		ResColorPaper[1]++;
	}

	return;
}

int solution() {
	// 1이 붙여진 격자 갯수와 벡터에 담기
	vector<pair<int, int>> OnePaper;
	int resOnePaper = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (MAP[i][j] == 1) {
				resOnePaper++;
				OnePaper.push_back({ i, j });
			}
		}
	}

	// 색종이가 붙여진 영역을 표시하기 위한 맵
	vector<vector<bool>> visitedMap(10, vector<bool>(10, false));
	vector<int> ResColorPaper(5 + 1, 5);
	
	DFS(resOnePaper, 0, visitedMap, ResColorPaper, OnePaper, 0);

	if (MIN_ANSWER == MAX)
		return -1;

	return MIN_ANSWER;
}

int main() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> MAP[i][j];
		}
	}

	int answer = solution();
	cout << answer << endl;

	return 0;
}