์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ๊ทธ๋ƒฅ ์กฐ๊ฑด์— ๋งž์ถฐ์„œ ํ’€๋ฉด ๋˜๋Š” ๋ฌธ์ œ์ด๋‹ค.
  • ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ์‚ฌ๊ฐํ˜•์— ๋Œ€ํ•ด ๊ฒ€์‚ฌํ•˜๊ณ , pcl์„ ๋ฝ‘์•„๋‚ธ ๋‹ค์Œ์—, ๋งˆ์ง€๋ง‰์œผ๋กœ โ€˜๋‹ค๋ฅธ pcl์— ํฌํ•จ๋˜๋Š” pclโ€™์„ ์ œ๊ฑฐํ•˜๊ณ  ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค.
  • โ€˜ํ•œ ์ƒ‰์€ ์—ฐ์†๋œ ์ง€์—ญ์ด ํ•˜๋‚˜์ด๊ณ , ๋‹ค๋ฅธ ์ƒ‰์€ ๋‘๊ฐœ ์ด์ƒ์ด์–ด์•ผํ•œ๋‹ค. โ€™ ๋ผ๋Š” ์กฐ๊ฑด์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ•˜๋ฉด๋œ๋‹ค.
    • ์ธ์ ‘ํ•œ ๊ฐ™์€ ์ƒ‰์— ๋Œ€ํ•ด์„œ๋งŒ BFS๋ฅผ ์ง„ํ–‰ํ•˜๊ณ , BFS ์ง„ํ–‰๋œ ์ด ์ˆ˜ t๋ฅผ ์„ผ๋‹ค.
    • t๊ฐ€ ํ˜„์žฌ ์ง€์—ญ์—์„œ ๊ทธ ์ƒ‰์˜ ์ˆ˜์™€ ๊ฐ™์œผ๋ฉด ์ฒซ๋ฒˆ์งธ ์กฐ๊ฑด์ด ๋งŒ์กฑ๋˜์—ˆ๋‹ค๊ณ  ํ‘œ์‹œ, ๊ทธ๊ฒƒ์ด ์•„๋‹ˆ๋ผ๋ฉด ๋‘๋ฒˆ์งธ ์กฐ๊ฑด์ด ๋งŒ์กฑํ–ˆ๋‹ค๊ณ  ํ‘œ์‹œํ•˜๋Š”๋ฐ, ๋‘๋ฒˆ์งธ ์กฐ๊ฑด์€ ๋งŒ์กฑํ• ๋•Œ๋งˆ๋‹ค 1์„ ๋”ํ•ด์ฃผ๋Š” ์นด์šดํ„ฐ๋กœ ํ‘œํ˜„ํ•˜์ž.
    • ์œ„์™€๊ฐ™์ด ํ•˜๋ฉด
      • โ€˜์—ฐ์†๋œ ์ง€์—ญ์ด ํ•˜๋‚˜์ธ ์ƒ‰โ€™์ด ์—†์„ ๊ฒฝ์šฐ ์ฒซ๋ฒˆ์งธ ์กฐ๊ฑด์ด ๋งŒ์กฑํ•˜์ง€ ์•Š์Œ
      • ๋‘ ์ƒ‰ ๋ชจ๋‘ ํ•˜๋‚˜๋กœ ์—ฐ๊ฒฐ๋˜์—ˆ์„๋•Œ๋Š” ๋‘๋ฒˆ์งธ ์กฐ๊ฑด์ด ๋งŒ์กฑ๋˜์ง€ ์•Š์Œ.
      • ๋”ฐ๋ผ์„œ ์ •๋‹ต์ผ๋•Œ๋งŒ pcl์— ์ถ”๊ฐ€ํ•ด์ค„ ์ˆ˜ ์žˆ๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
char map[22][22];
int n, colorCheck[26], os[4][2] = { {-1,0}, {0,1}, {1,0},{0,-1} };
vector<pair<pair<int, int>, pair<int, int>>> pcl;
bool visit[22][22];
pair<int, int> q[420];
 
void getPCL();
void checkSingleRectagle(int, int,int,int);
 
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	getPCL();
 
	int last = pcl.size() - 1;
	for (int i = last; i >=0; i--) {
		int si = pcl[i].first.first, sj = pcl[i].first.second, w = pcl[i].second.first, h = pcl[i].second.second;
		for (int j = 0; j < i; j++)
			if (si >= pcl[j].first.first && sj >= pcl[j].first.second && w <= pcl[j].second.first && h <= pcl[j].second.second) {
				pcl.pop_back();
				break;
			}
	}
 
	cout << pcl.size() << endl;
}
 
void getPCL() {
	for (int h = n - 1; h >= 0; h--) {
		for (int w = n - 1; w >= 0; w--) {
			for (int i = 0; i < n - w; i++) {
				for (int j = 0; j < n - h; j++) {
					checkSingleRectagle(i, j, i + w, j + h);
					memset(colorCheck, 0, sizeof(colorCheck));
				}
			}
		}
	}
}
 
void checkSingleRectagle(int si, int sj, int w, int h) {
	for (int i = 0; i < pcl.size(); i++)
		if (si >= pcl[i].first.first && sj >= pcl[i].first.second && w <= pcl[i].second.first && h <= pcl[i].second.second)
			return;
 
	int count = 0;
	for (int i = sj; i <= h; i++) {
		for (int j = si; j <= w; j++) {
			if (!colorCheck[map[i][j] - 'A'])
				count++;
			colorCheck[map[i][j] - 'A']++;
			if (count > 2)
				return;
		}
	}
	if (count != 2)
		return;
 
 
	bool check1 = false;
	int check2 = 0;
	for (int i = sj; i <= h; i++) {
		for (int j = si; j <= w; j++) {
			if (!visit[i][j]) {
				char c = map[i][j];
				int temp = colorCheck[c - 'A'], curIdx = 0, lastIdx = 0;
				visit[i][j] = true;
				q[lastIdx++] = { i,j };
				while (curIdx != lastIdx) {
					int ch = q[curIdx].first, cc = q[curIdx].second;
					curIdx++;
					temp--;
 
					for (int k = 0; k < 4; k++) {
						int nh = ch + os[k][0], nc = cc + os[k][1];
						if (nh >= sj && nh <= h && nc >= si && nc <= w && !visit[nh][nc] && map[nh][nc] == c) {
							q[lastIdx++] = { nh, nc };
							visit[nh][nc] = true;
						}
					}
				}
				if (temp == 0)
					check1 = true;
				else
					check2++;
			}
			if (check1 && check2 >= 2)
				break;
		}
	}
	memset(visit, 0, sizeof(visit));
 
	if (check1 && check2 >= 2)
		pcl.push_back({ {si, sj}, { w, h} });
}