[BOJ] 17140 이차원 배열과 연산

1. 문제 요약

입력으로

r

c

k

가 주어지고,

{arr[r][c] = k}

가 되려면 연산을 몇 번 수행해야 하는지 구해야 한다.

{1 <= r, c, k <= 100}

초기 배열은 3x3이고, 1초마다 배열에 연산을 한 번씩 적용한다.

행의 개수 >= 열의 개수일 경우, 배열의 모든 행에 대해서 정렬을 수행한다.
행의 개수 < 열의 개수일 경우, 배열의 모든 열에 대해서 정렬을 수행한다.

여기에서 말하는 정렬 연산은 이렇게 정의된다.

각 행/열을 구성하는 수가 각각 몇 번 나왔는지 알아본다. (ex. 1이 1번, 2가 3번, 3이 1번, ...)
수의 등장 횟수를 오름차순으로, 등장 횟수가 같다면 수를 오름차순으로 정렬한다.
정렬된 결과를 배열 A에 다시 넣는다. 이 때, 각 행/열의 크기가 각각 다를 수 있다. 빈 칸에는 0을 넣는다. (0은 정렬할 때 무시된다.)

예를 들어서, 1, 1, 3이라는 행이 있다면, 1이 2번, 3이 1번 나왔으므로 3, 1, 1, 2처럼 정렬된다.

2. 풀이 정리

다음과 같은 점들을 보아 100초동안 모든 경우를 탐색하면 될 것 같았다.

100초를 넘어가면 더이상 연산을 수행하지 않는다
r, c, k의 범위가 100 이하로 굉장히 작다
중간 연산의 결과로 만들어지는 배열도 200x200로 작은 편이다
배열에서 100을 넘어가는 숫자는 나오지 않을 것이다

R연산과 C연산을 언제 수행하는지가 명확하기 때문에,

{arr[r][c]}

가

k

가 될 때까지, 또는 100초에 도달할 때까지 정해진 연산을 수행하면 된다.

나는 solve함수에서 연산을 수행했다.

현재 행의 숫자(
R
)과 열의 숫자(
C
)를 비교하여 올바른 연산을 수행한다.
- R 연산의 경우, 모든 행에 대하여, 숫자 갯수를 센다.
- 그리고 등장 횟수가 0이 아닌 수들을 priority queue에 { 수의 등장 횟수, 수 } pair를 push해준다.
- pq에서 pair를 하나씩 뽑으면서 tmp 배열을 채워주고, 이 과정에서 정렬 연산이 끝난 후 열의 길이도 구해준다.
- tmp배열을 arr 배열에 복사하고, 열의 길이를 갱신한다.
- 만약
  {arr[r][c]} = k
  가 되었다면, 답을 출력한다.
- C 연산은 행과 열을 바꾸어 수행하면 된다.

3. 구현

나는 배열의 시작을 0으로 잡았기 때문에 r - 1, c - 1등으로 인덱싱했다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
# define endl '\n'
#define pii pair<int, int>
using namespace std;

int r, c, k;
int arr[205][205];
int tmp[205][205];
int R = 3, C = 3;
bool flag = false;

void solve() {
	priority_queue<pii, vector<pii>, greater<pii> > pq;

	int nexR = R, nexC = C;

	if (R >= C) {
		for (int rr = 0; rr < R; rr++) {
			int count[105] = { 0, };
			for (int cc = 0; cc < C; cc++) {
				count[arr[rr][cc]]++;
			}

			for (int i = 1; i <= 100; i++) {
				if (count[i]) pq.push({ count[i], i });
			}

			for (int i = 0; i < 100; i++) {
				if (!pq.empty()) {
					tmp[rr][i * 2] = pq.top().second;
					tmp[rr][i * 2 + 1] = pq.top().first;
					pq.pop();
					nexC = max(nexC, i * 2 + 2);
				}
				else {
					tmp[rr][i * 2] = 0;
					tmp[rr][i * 2 + 1] = 0;
				}
			}

			for (int cc = 0; cc < nexC; cc++) {
				arr[rr][cc] = tmp[rr][cc];
			}
		}
	}
	else {
		for (int cc = 0; cc < C; cc++) {
			int count[105] = { 0, };
			for (int rr = 0; rr < R; rr++) {
				count[arr[rr][cc]]++;
			}

			for (int i = 1; i <= 100; i++) {
				if (count[i]) pq.push({ count[i], i });
			}

			for (int i = 0; i < 100; i++) {
				if (!pq.empty()) {
					tmp[i * 2][cc] = pq.top().second;
					tmp[i * 2 + 1][cc] = pq.top().first;
					pq.pop();
					nexR = max(nexR, i * 2 + 2);
				}
				else {
					tmp[i * 2][cc] = 0;
					tmp[i * 2 + 1][cc] = 0;
				}
			}

			for (int rr = 0; rr < nexR; rr++) {
				arr[rr][cc] = tmp[rr][cc];
			}
		}
	}

	R = nexR;
	C = nexC;

	if (arr[r - 1][c - 1] == k) {
		flag = true;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> r >> c >> k;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}
	
	if (arr[r - 1][c - 1] == k) {
		cout << 0;
		return 0;
	}

	int count = 0;
	while (!flag && count++ <= 100) {
		solve();
	}

	if (flag) {
		cout << count;
	}
	else {
		cout << -1;
	}
	
	return 0;
}

[BOJ] 17140 이차원 배열과 연산

Table Of Contents

1. 문제 요약

2. 풀이 정리

3. 구현