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

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

---

[ 알고리즘풀이 ]

 자료구조 우선순위큐를 이용하면 조금 더 간단하게 해결할 수 있는 문제입니다.

1. R연산

- 원소의 값이 1 ~ 100 사이이므로, count 배열을 선언해 행을 순회하며 값들을 count 한다. 이때, count된 값들은 0으로 초기화한다.

- count한 값들을 오름차순 기준 우선순위큐에 (count, 해당 index) 를 push 한다.

- 우선순위큐의 원소를 하나씩 뽑아가며 map에 갱신한다.

2. C연산

- 위의 과정을 열을 순회하며 진행하면 된다.

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int map[100][100] = {};
int r, c, k, t, row = 3, col = 3;

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

	cin >> r >> c >> k;
	r--, c--;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			cin >> map[i][j];

	int ans = 0;
	while (map[r][c] != k && ans <= 100) {
		if (row >= col) { //R연산
			int m = -1;
			for (int i = 0; i < row; i++) {
				priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
				int count[101] = {};
				// 행을 순회하며 count
				for (int j = 0; j < col; j++){
					count[map[i][j]]++;
					map[i][j] = 0;
				}
				// count를 기준으로 정렬
				for (int j = 1; j <= 100; j++)
					if (count[j])
						pq.push(make_pair(count[j], j));
				// 정렬된 새로운 값들을 대입하기.
				m = max(m, int(pq.size() * 2));
				int len = pq.size();
				for (int j = 0; j < len && j < 50; j++) {
					map[i][2 * j] = pq.top().second;
					map[i][2 * j + 1] = pq.top().first;
					pq.pop();
				}
			}
			// row, col 갱신
			col = m;
		}
		else { //C연산
			int m = -1;
			priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
			for (int j = 0; j < col; j++) {
				int count[101] = {};
				// 행을 순회하며 count
				for (int i = 0; i < row; i++){
					count[map[i][j]]++;
					map[i][j] = 0;
				}
				// count를 기준으로 정렬
				for (int i = 1; i <= 100; i++)
					if (count[i])
						pq.push(make_pair(count[i], i));
				// 정렬된 새로운 값들을 대입하기.
				m = max(m, int(pq.size() * 2));
				int len = pq.size();
				for (int i = 0; i < len && i < 50; i++) {
					map[2 * i][j] = pq.top().second;
					map[2 * i + 1][j] = pq.top().first;
					pq.pop();
				}
			}
			// row, col 갱신
			row = m;
		}
		ans++;
	}

	if (ans > 100)
		cout << -1;
	else
		cout << ans;
}

---