📂 PS

/

📖 BOJ

/

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

[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함수에서 연산을 수행했다.

  1. 현재 행의 숫자(
    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;
}