C++:: boj 17140 < 이차원 배열과 연산 >

행렬을 잘 다뤄야 하는 문제이다. 주의해야 할 점이 좀 몇가지가 있는데 행과 열을 대칭으로 바꿔서 정렬을 해준다음 다시 대칭으로 변환하여 열에 대한 정렬을 해줄 떄 복사의 범위가 행열중 큰 수까지 복사되어야 한다는 점이다. 또한 문제에서 100 초가 넘어가거나 행렬의 길이가 100이 넘어갈 때의 처리를 문제설명에서 명시하기에 문제를 주의깊게 읽어야한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int r,c,k,answer;
int r_size = 3, c_size = 3;
vector<vector<int>> A(100, vector<int>(100));
unordered_map<int, int> um;

bool compare(pair<int,int>& p_a, pair<int,int>& p_b) {
	if (p_a.second == p_b.second) return p_a.first < p_b.first;
	return p_a.second < p_b.second;
}

void sortArr() {// 행 정렬
	int len = 0;
	for (int i=0; i<r_size; i++) {
		um.clear();
		for (int j=0; j<c_size; j++) {
			if (A[i][j]) um[A[i][j]]++;
		}
		vector<pair<int,int>> res;
		for (auto& num : um) {
			res.push_back({num.first, num.second});
		}
		sort(res.begin(), res.end(), compare);
		fill(A[i].begin(), A[i].end(), 0);
		for (int j=0; j<res.size(); j++) {
			if (j*2 >= 100) break;
			A[i][j*2] = res[j].first;
			A[i][j*2+1] = res[j].second;
		}
		len = max(len, static_cast<int>(res.size()*2));
	}
	if (len > 100) len = 100;
	c_size = len;
}

void flipArr() {// 대칭으로 행렬을 뒤집는다.
	int size = max(r_size, c_size);// 가장 큰 행렬크기까지 복사해야한다.
	for (int i=0; i<size; i++) {
		for (int j=i+1; j<size; j++) {
			swap(A[i][j], A[j][i]);
		}
	}
}

int main() {
	cin >> r >> c >> k;
	for (int i=0; i<3; i++) {
		for (int j=0; j<3; j++) {
			cin >> A[i][j];
		}
	}
	r--; c--;
	while (A[r][c]!=k && answer <= 100) {
		bool flip = false;
		if (r_size < c_size) {// C연산이면
			flip = true;
			flipArr();
			swap(r_size, c_size);
		}
		sortArr();
		if (flip) {
			flipArr();
			swap(r_size, c_size);
		}
		answer++;
	}
	if (answer > 100) answer = -1;
	cout << answer << "\n";
}