문제 : https://www.acmicpc.net/problem/17140

서론

시뮬레이션 문제.

시뮬레이션 문제는 지문을 꼼꼼히 읽고 처음부터 실수가 없는것이 중요하다.

아이디어

R연산과 C연산을 구현하는게 핵심이다.

R연산을 예로 들어서

배열의 모든 행에서 각 행마다 어떤 숫자가 몇개인지 체크하기 위해서 check 배열을 만들어준다.

어떤 행이 [1,2,1] 일 때

check[1]++;

check[2]++;

check[1]++;

해주면 check배열값은 0,2,1,0,0,....로 check[1] = 2, check[2] = 1 처럼 어떤 값이 몇개인지 알 수 있다.

각 행에서 어떤 숫자가 몇개인지 알아냈다면 그것을 정렬해야한다.

1이 두개, 2가 하나면 [2,1,1,2]로 정렬해야한다.

1차적으로 개수를 기준으로 오름차순하고 2차적으로 값을 기준으로 오름차순한다.

만들어둔 check 배열을 그냥 정렬해버리면 인덱스가 틀어져서 어떤 값이 몇개인지 알아낼 수 없으므로

새로 벡터를 만들어서 어떤 값이 몇개인지를 같이 넣어준다.

v.push_back({ckeck[i], i})

위와 같이 v의 first값은 숫자의 개수, second값은 숫자가 들어가게 하고 오름차순으로 정렬하면

1차는 숫자의 개수, 2차는 숫자를 기준으로 정렬된다.

정렬했으면 다시 행에 넣어줘야한다.

[v[0].second, v[0].first, v[1].second, v[1].first.............]로 넣어준다.

그리고 벡터 사이즈 *2 이후 칸들은 0으로 채워준다.

위의 1, 2번을 위해서는 행의 개수와 열의 개수를 알아야하고 R연산을 할때마다 갱신해줘야한다.

R연산을 하게되면 행의 개수는 바뀌지 않고 열의 개수만 바뀐다. (연산을 하면 열의 개수가 늘어날수도 있지만 줄어들 수도 있다.)

초기 행의 개수와 열의 개수는 3이고

R연산을 하고 만들어진 새로운 열의 개수는 벡터사이즈*2다.

구현

//c++

#include <iostream>
#include <algorithm>
#include <vector>

int a[101][101];
int r, c, k;
int cntR = 3;
int cntC = 3;

void fr() {
	int cnt = 0;
	for (int i = 0; i < cntR; i++) {

		int check[102] = { 0, };
		for (int j = 0; j < cntC; j++) {
			check[a[i][j]]++;
		}

		std::vector<std::pair<int, int>>v;
		for (int j = 1; j < 101; j++) {
			if (check[j] > 0) {
				v.push_back({ check[j], j });
			}
		}

		sort(v.begin(), v.end());

		int idx = 0;
		int size = v.size();
		for (int j = 0; j < size; j++) {
			a[i][idx] = v[j].second;
			a[i][idx + 1] = v[j].first;
			idx += 2;
		}
		cnt = std::max(cnt, size*2);

		for (int j = idx; j < 101; j++) a[i][j] = 0;
	}
	cntC = cnt;
}

void fc() {
	int cnt = 0;
	for (int i = 0; i < cntC; i++) {

		int check[102] = { 0, };
		for (int j = 0; j < cntR; j++) {
			check[a[j][i]]++;
		}
		std::vector<std::pair<int, int>>v;
		for (int j = 1; j < 101; j++) {
			if (check[j] > 0) {
				v.push_back({ check[j], j });
			}
		}

		sort(v.begin(), v.end());

		int idx = 0;
		int size = v.size();
		for (int j = 0; j < size; j++) {
			a[idx][i] = v[j].second;
			a[idx + 1][i] = v[j].first;
			idx += 2;
		}
		cnt = std::max(cnt, size*2);

		for (int j = idx; j < 101; j++) a[j][i] = 0;
	}
	cntR = cnt;
}

int main() {
	int time = 0;

	std::cin >> r >> c >> k;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			std::cin >> a[i][j];
		}
	}

	while (time <= 100) {
		if (a[r - 1][c - 1] == k) break;
		time++;
		if (cntR >= cntC) fr(); 
		else  fc();
	}

	if (time > 100) std::cout << "-1";
	else std::cout << time;

}