백준 이차원 배열과 연산 17140 C++

1. 문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

 

2. 입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

 

3. 출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

 

4. 풀이방법

 

이 문제는 simulation 문제였다. 최소값이라고 적혀있어서 헷갈릴 수 있지만 구현을 해서 확인하면 되는 문제이다.

 

먼저 메인 함수는 아래와 같다.

 

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> r >> c >> k;
	for (int i = 0;i < 3;i++) {
		for (int j = 0;j < 3;j++) {
			cin >> arr[i][j];
		}
	}
	while (1) {
		if (arr[r-1][c-1] == k) {
			break;
		}
		if (total > 100){
			break;
		}
		if (r_cnt >= c_cnt) {
			row_cal();
		}
		else {
			col_cal();
		}
		total++;
	}
	if (total > 100) {
		cout << "-1" << endl;
	}
	else {
		cout << total << endl;
	}
	return 0;
}

 

입력을 받은 다음에 arr[r-1][c-1] 의 값이 k가 되면 break 한다.

 

void row_cal(void) {
	int tmp = -1;
	for (int i = 0;i < r_cnt ;i++) {  // 각 행에 대해서 수행한다
		// 1 . 행을 돌면서 각각 몇번이 있는지 확인한다
		memset(num, 0, sizeof(num));
		for (int j = 0;j < c_cnt;j++) {
			if (arr[i][j] != 0) {
				num[arr[i][j]]++;
			}
		}
		// 2. 벡터에 (숫자, 나온 횟수) 가 나오게 저장한다
		vector<pair<int, int>> v;
		for (int j = 1;j < 101;j++) {
			if (num[j] != 0) {
				v.push_back({ j, num[j] });
			}
		}
		// 3. 벡터를 정렬한다.
		sort(v.begin(), v.end(), cmp1);
		// arr에 반영한다
		int loc = 0;
		for (int j = 0;j < v.size();j++) {
			arr[i][loc++] = v[j].first;
			arr[i][loc++] = v[j].second;
		}
		for (int j = loc;j < c_cnt; j++) {
			arr[i][j] = 0; // 나머지 부분을 0으로 초기화
		}
		c_cnt = max(c_cnt, int(v.size()) * 2);
		//tmp = max(tmp, loc);
	}
	return;
}

 

row에 대해서 돌려주는 방식이다.

각 행에 대해 수행하고, 행을 돌면서 number가 각각 몇번이 나오는지 센다.

그 후에 벡터에 (숫자, 나온횟수)가 나오게 저장한다.

 

벡터를 정렬한 다음에 arr에 반영하면 완료된다.

 

#include <iostream>
#include <functional>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int r, c, k, r_cnt=3, c_cnt=3;
int arr[101][101];
int total;
int num[101];

/*
	정렬방식
	1. 숫자의 등장 횟수가 커지는 순으로 정렬한다
	2. 만약 등장횟수가 같다면 수가 큰 순으로 정렬한다
*/
bool cmp1(pair<int, int> v1, pair<int, int> v2) {
	if (v1.second != v2.second) {
		return v1.second < v2.second;
	}
	else {
		return v1.first < v2.first;
	}
}
void row_cal(void) {
	int tmp = -1;
	for (int i = 0;i < r_cnt ;i++) {  // 각 행에 대해서 수행한다
		// 1 . 행을 돌면서 각각 몇번이 있는지 확인한다
		memset(num, 0, sizeof(num));
		for (int j = 0;j < c_cnt;j++) {
			if (arr[i][j] != 0) {
				num[arr[i][j]]++;
			}
		}
		// 2. 벡터에 (숫자, 나온 횟수) 가 나오게 저장한다
		vector<pair<int, int>> v;
		for (int j = 1;j < 101;j++) {
			if (num[j] != 0) {
				v.push_back({ j, num[j] });
			}
		}
		// 3. 벡터를 정렬한다.
		sort(v.begin(), v.end(), cmp1);
		// arr에 반영한다
		int loc = 0;
		for (int j = 0;j < v.size();j++) {
			arr[i][loc++] = v[j].first;
			arr[i][loc++] = v[j].second;
		}
		for (int j = loc;j < c_cnt; j++) {
			arr[i][j] = 0; // 나머지 부분을 0으로 초기화
		}
		c_cnt = max(c_cnt, int(v.size()) * 2);
		//tmp = max(tmp, loc);
	}
	return;
}

void col_cal(void) {
	int tmp = -1;
	for (int i = 0;i < c_cnt;i++) {  
		// 1 . 행을 돌면서 각각 몇번이 있는지 확인한다
		memset(num, 0, sizeof(num));
		for (int j = 0;j < r_cnt;j++) {
			if (arr[j][i] != 0) {
				num[arr[j][i]]++;
			}
		}
		// 2. 벡터에 (숫자, 나온 횟수) 가 나오게 저장한다
		vector<pair<int, int>> v;
		for (int j = 1;j < 101;j++) {
			if (num[j] != 0) {
				v.push_back({ j, num[j] });
			}
		}
		// 3. 벡터를 정렬한다.
		sort(v.begin(), v.end(), cmp1);
		// arr에 반영한다
		int loc = 0;
		for (int j = 0;j < v.size();j++) {
			arr[loc++][i] = v[j].first;
			arr[loc++][i] = v[j].second;
		}
		for (int j = loc;j < c_cnt; j++) {
			arr[j][i] = 0; // 나머지 부분을 0으로 초기화
		}
		tmp = max(tmp, loc);
		r_cnt = max(r_cnt, int(v.size()) * 2);
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> r >> c >> k;
	for (int i = 0;i < 3;i++) {
		for (int j = 0;j < 3;j++) {
			cin >> arr[i][j];
		}
	}
	while (1) {
		if (arr[r-1][c-1] == k) {
			break;
		}
		if (total > 100){
			break;
		}
		if (r_cnt >= c_cnt) {
			row_cal();
		}
		else {
			col_cal();
		}
		total++;
	}
	if (total > 100) {
		cout << "-1" << endl;
	}
	else {
		cout << total << endl;
	}
	return 0;
}