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

[이차원 배열과 연산] https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

R연산과 C연산을 코드로 구현하는 문제인 것 같다.

정렬 시 우선순위 큐를 이용하면 쉽게 구현할 수 있다.

 

우선순위 큐를 사용할 때 자료형으로 pair을 사용하면,

pair<a, b> 일 경우에 a값이 같으면 b의 값을 기준으로 우선순위가 결정된다.

 

[ 소스 코드 ]

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 101

using namespace std;

typedef pair<int, int> tmp; //first : cnt, second : num
int r, c, k, r_size = 3, c_size = 3;
int A[MAX][MAX];

int solve();
void operR();
void operC();
int main() {
	scanf("%d %d %d", &r, &c, &k);

	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			scanf("%d", &A[i][j]);
		}
	}

	printf("%d\n", solve());

	return 0;
}

int solve() {
	int time = 0;

	while(time < 101) {
		if (A[r][c] == k) return time;

		if (r_size >= c_size)  operR();
		else operC();

		time++;
	}

	return -1;
}

void operR() {
	priority_queue<tmp, vector<tmp>, greater<tmp> > q;
	vector <int> v;
	int size = 0;

	for (int i = 1; i <= r_size; i++) {
		for (int j = 1; j <= c_size; j++) {
			if (!A[i][j]) continue;
			v.push_back(A[i][j]);
			A[i][j] = 0;
		}

		sort(v.begin(), v.end());
		pair<int, int> val = make_pair(1, v[0]);
		for (int j = 1; j < v.size(); j++) {
			if (val.second == v[j]) val.first++;
			else {
				q.push(val);
				val.first = 1;
				val.second = v[j];
			}
		}
		q.push(val);
		v.clear();
		
		int idx = 1;
		while (!q.empty()) {
			if (idx < 101) {
				A[i][idx++] = q.top().second;
				A[i][idx++] = q.top().first;
			}
			q.pop();
		}
		size = max(size, idx-1);
	}
	c_size = size;
}

void operC() {
	priority_queue<tmp, vector<tmp>, greater<tmp> > q;
	vector <int> v;
	int size = 0;

	for (int i = 1; i <= c_size; i++) {
		for (int j = 1; j <= r_size; j++) {
			if (!A[j][i]) continue;
			v.push_back(A[j][i]);
			A[j][i] = 0;
		}

		sort(v.begin(), v.end());
		pair<int, int> val = make_pair(1, v[0]);
		for (int j = 1; j < v.size(); j++) {
			if (val.second == v[j]) val.first++;
			else {
				q.push(val);
				val.first = 1;
				val.second = v[j];
			}
		}
		q.push(val);
		v.clear();

		int idx = 1;
		while (!q.empty()) {
			if (idx < 101) {
				A[idx++][i] = q.top().second;
				A[idx++][i] = q.top().first;
			}
			q.pop();
		}
		size = max(size, idx-1);
	}
	r_size = size;
}