Algorithm/구현(Brute force, Back tracking, etc.)

백준 17140 이차원 배열과 연산

쩡류 2021. 3. 4. 17:11
728x90

while문을 통해 answer<= 100인 조건 적용하고,

만약 문제에 주어진 arr[r][c] == k 조건을 만족하면 break 하도록 조건 걸어준다.

while문 내부에서는

 

1. 행의 갯수 >= 열의 갯수 시 'r연산' 적용


  0. 가장 먼저, vector<int> 벡터를 만든다.(한 개의 행마다 진행할 것임)
  1. for문 통해 해당 행에 있는 숫자 갯수 조사 후(index 사용) pair쌍을 벡터에 push_back 

  2. 내가 정해둔 기준에 따라 벡터를 정렬한다. (second 먼저 비교하고 그 다음 first 순으로 오름차순 정렬)
  3. 벡터를 for문으로 돌리면서 arr를 최신화. 이 때 size 비교하면서 max 조사한다. max * 2가 결국 다음 col  값이 된다.
  4. index 초기화 후 다음 행 진행

  5. 만약 모든 행 연산 완료시 col 최신화

2. else 'c연산' 적용

 

  0. 가장 먼저, vector<int> 벡터를 만든다.(한 개의 열마다 진행할 것임)
  1. for문 통해 해당 열에 있는 숫자 갯수 조사 후(index 사용) pair쌍을 벡터에 push_back

  2. 내가 정해둔 기준에 따라 벡터를 정렬한다.
  3. 벡터를 for문으로 돌리면서 arr를 최신화. 이 때 size 비교하면서 max 조사한다. max * 2가 결국 다음 col  값이 된다.
  4. index 초기화 후 다음 행 진행

  5. 만약 모든 행 연산 완료시 col 최신화

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX 101
using namespace std;
int arr[MAX][MAX]; //
int num_index[101];
bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second)
		return a.first < b.first;
	else return a.second < b.second;
}
int main() {
	int r, c, k;
	cin >> r >> c >> k;
	int num_row = 3;
	int num_col = 3;
	for (int i = 0; i < num_row; i++) {
		for (int j = 0; j < num_col; j++) {
			cin >> arr[i][j];
		}
	}
	int answer = 0;
	while (answer <= 100) {
		if (r-1 < num_row && c-1 < num_col && arr[r-1][c-1] == k) break;
		if (num_row >= num_col) { // r연산
			int max_length_of_col = num_col;
			for (int i = 0; i < num_row; i++) {
				int temp_max = 0; // 배열 내부 값 중 가장 큰 값을 저장. 
				for (int j = 0; j < num_col; j++) {
					if (!arr[i][j]) continue;
					num_index[arr[i][j]]++;
					temp_max = max(temp_max, arr[i][j]);
				}
				vector<pair<int,int>> temp_v2;
				for (int j = 1; j <= temp_max; j++) {
					if (num_index[j] != 0) temp_v2.push_back({ j,num_index[j] });
				}
				sort(temp_v2.begin(), temp_v2.end(), compare);
				max_length_of_col = max(max_length_of_col, int(temp_v2.size() * 2));
				for (int j = 0; j < temp_v2.size(); j++) {
					arr[i][j * 2] = temp_v2[j].first;
					arr[i][j * 2 + 1] = temp_v2[j].second;
				}
				for (int j = temp_v2.size()*2; j < num_col; j++) arr[i][j] = 0;
				memset(num_index, 0, sizeof(num_index));
			}
			num_col = max_length_of_col;
		}
		else { // c연산
			int max_length_of_row = num_row;
			for (int i = 0; i < num_col; i++) {
				int temp_max = 0; // 배열 내부 값 중 가장 큰 값을 저장. 
				for (int j = 0; j < num_row; j++) {
					if (!arr[j][i]) continue;
					num_index[arr[j][i]]++;
					temp_max = max(temp_max, arr[j][i]);
				}
				vector<pair<int, int>> temp_v2;
				for (int j = 1; j <= temp_max; j++) {
					if (num_index[j] != 0) temp_v2.push_back({ j,num_index[j] });
				}
				sort(temp_v2.begin(), temp_v2.end(), compare);
				max_length_of_row = max(max_length_of_row, int(temp_v2.size() * 2));
				for (int j = 0; j < temp_v2.size(); j++) {
					arr[j*2][i] = temp_v2[j].first;
					arr[j*2+1][i] = temp_v2[j].second;
				}
				for (int j = temp_v2.size()*2; j < num_row; j++) arr[j][i] = 0;
				memset(num_index, 0, sizeof(num_index));
			}
			num_row = max_length_of_row;
		}
		answer++;
	}
	if (answer > 100) answer = -1;
	cout << answer << '\n';
	return 0;
}