[PS][기출문제][삼성]/[BOJ][17140][이차원 배열과 연산]

boj17140.cpp

#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

int r = 0, c = 0, k = 0;
int map[201][201];
int cnt[101];
int w =3, h = 3;
vector<pair<int, int> > v;
bool check(void) {
	//cout << r - 1 << "," << c - 1 << "," << map[r - 1][c - 1] << "\n";
	return map[r-1][c-1] != k;
}

void cntshow(void) {
	for (int i = 0; i < 10; i++) {
		cout << i << ' ';
	}
	cout << "\n";
	for (int i = 0; i < 10; i++) {
		cout << cnt[i] << ' ';
	}
	cout << "\n";
}

void show(void) {
	//cout << "===============\n";
	//for (int i = 0; i < h; i++) {
	//	for (int j = 0; j < w; j++) {
	//		cout << map[i][j] << ' ';
	//	}
	//	cout << "\n";
	//}
	//cout << "===============\n";
}

bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) return  a.second < b.second;
	else return a.first < b.first;
}

int solve(void) {
	int ret = 0;
	int te= 0; //total element
	int ce = 0;//current element
	int time = 1;
	while(check()){
		ret++;
		if (ret > 100) return -1;
		//r연산
		if (h >= w) {
			for (int i = 0; i < h; i++) {
				te = 0;
				ce = 0;
				//카운팅
				for (int j = 0; j < w; j++) {
					if (map[i][j] == 0) continue;
					if (cnt[map[i][j]] == 0) te += 1;
					cnt[map[i][j]] += 1;
				}
				for (int j = 1; j <= 100; j++) {
					if (cnt[j]) {
						v.push_back(make_pair(j, cnt[j]));
					}
					cnt[j] = 0;
				}
				sort(v.begin(),v.end(), compare);

				//row 초기화
				memset(map[i], 0, sizeof(map[i]));
				//채워넣기

				for (int j = 0; j < v.size(); j++) {
					map[i][ce++] = v[j].first;
					map[i][ce++] = v[j].second;
				}
				w = w < 2 * te ? 2 * te : w;
				v.clear();
			}
			show();
		}
		//c연산
		else {
			for (int j = 0; j < w; j++) {
				te = 0;
				ce = 0;
				//카운팅
				for (int i = 0; i < h; i++) {
					if (map[i][j] == 0) continue;
					if (cnt[map[i][j]] == 0) te += 1;
					cnt[map[i][j]] += 1;
				}
				for (int i = 1; i <= 100; i++) {
					if (cnt[i]) {
						v.push_back(make_pair(i, cnt[i]));
					}
					cnt[i] = 0;
				}
				sort(v.begin(), v.end(), compare);

				//row 초기화
				for (int i = 0; i < h; i++) {
					map[i][j] = 0;
				}
				//채워넣기
				for (int i = 0; i < v.size(); i++) {
					map[ce++][j] = v[i].first;
					map[ce++][j] = v[i].second;
				}
				h = h < 2 * te ? 2 * te : h;
				v.clear();
			}
			show();
		}
	}
	return ret;

}
int main(void) {
	cin >> r>> c>> k;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> map[i][j];
		}
	}
	cout<< solve()<<"\n";
	return 0;
}