백준 1780 c++ " 종이의 개수" -PlusUltraCode-

https://www.acmicpc.net/problem/1780

 

[필자 사고]

분할정복 문제다.

분할 정복 알고리즘을 구현하기 위해서는 크기를 나누는 기준이 중요하고 

DFS를 이용해야 한다.

그리고 마지막 종료 조건 및 문제에서 요구하는 달성조건을 그대로 이용하면 쉽게 해결할 수 있다.

 

아래는 자세한 코드해설이다.

[코드 해설]

이 코드는 종이의 색상을 구분하는 분할 정복 문제입니다.
입력받은 N x N 정사각형 종이를 -1, 0, 1로 채운 후, 같은 수로만 이루어진 부분 종이를 세는 프로그램입니다.

---

🔹 main()

• Input()으로 2차원 배열을 입력받고
• Game_Start()로 DFS 분할 정복을 시작

---

🔹 Input()

• 정사각형 종이 크기 N 입력
• N x N 크기의 2차원 배열 arr을 선언하고 숫자들을 입력받아 저장

---

🔹 DFS(int sero, int garo, int size)

• 현재 (sero, garo)를 좌상단으로 하는 size x size 영역이 모두 같은 숫자인지 검사
• 모두 같으면 해당 숫자에 대응하는 카운터 증가 (minusCount, zeroCount, plusCount)
• 다르면 종이를 3등분하여 9개의 구역으로 나누고 각 구역에 대해 재귀 호출

기저 조건:

• size == 1이면 더 나눌 수 없으므로 해당 값의 카운트를 바로 증가시키고 종료

중간 조건:

• 현재 구역의 모든 값이 같으면 카운트 후 종료
• 다르면 size/3 크기의 구역 9개로 분할하고 각각 DFS 재귀 호출

---

🔹 Game_Start()

• 전체 종이(0,0,N)에 대해 DFS 실행
• 각 숫자 카운트를 출력

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> arr;
int N;
int minusCount = 0;
int zeroCount = 0;
int plusCount = 0;

void Input() {
	cin >> N;
	arr.assign(N, vector<int>(N));

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			int num;
			cin >> num;
			arr[i][k] = num;
		}
	}
}

void DFS(int sero, int garo, int size) {
	if (size == 1) {
		if (arr[sero][garo] == -1)minusCount++;
		else if (arr[sero][garo] == 0) zeroCount++;
		else if (arr[sero][garo] == 1)plusCount++;

		return;
	}
	int nowNumber = arr[sero][garo];
	bool sameFlag = true;
	for (int i = sero; i < sero + size; i++) {
		for (int k = garo; k < garo + size; k++) {
			if (nowNumber != arr[i][k]) {
				sameFlag = false;
				break;
			}
		}
		if (!sameFlag)break;
	}

	if (sameFlag == true) {
		if (arr[sero][garo] == -1)minusCount++;
		else if (arr[sero][garo] == 0) zeroCount++;
		else if (arr[sero][garo] == 1)plusCount++;

	}
	else {
		int nextSize = size / 3;
		for (int i = 0; i < 3; i++) {
			for (int k = 0; k < 3; k++) {
				DFS(sero + i * nextSize, garo + k * nextSize, nextSize);
			}
		}
	}
}

void Game_Start() {
	DFS(0, 0, N);
	cout << minusCount << '\n';
	cout << zeroCount << '\n';
	cout << plusCount << '\n';
}

int main(void) {
	Input();
	Game_Start();

}