[백준/BOJ] 백준 17140번 : 이차원 배열과 연산

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

코드에서는 행과 열의 시작을 0으로 했다. vector<pair<int, int>> count_num(101); 를 통해 개수, 숫자 정보를 저장하고 정렬을 해서 이용했고, vector<int> maked_vector; 를 통해 새로 만들어지는 열 또는 행을 저장했다. 

 

코드

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

int r, c, k;
int board[100][100];
int max_row = 3;
int max_col = 3;

void Pre_board()
{
	for (int i = 0; i < 100; i++)
		for (int j = 0; j < 100; j++)
			board[i][j] = 0;
}

int Solve(int cnt)
{
	//100초가 넘었을때
	if (cnt > 100)
		return -1;

	//board[r - 1][c - 1]에 k가 있을때
	if (board[r - 1][c - 1] == k)
		return cnt;

	//행의 개수가 더 클때
	if (max_row >= max_col)
	{
		int temp_max_col = -1;
		for (int i = 0; i < max_row; i++)
		{
			vector<pair<int, int>> count_num(101); //개수, 숫자정보를 저장
			vector<int> maked_vector; //새로 만들어지는 열을 저장

			for (int j = 0; j < 101; j++)
			{
				count_num[j] = make_pair(0, j); //각 수가 나온 개수를 0개로 초기화
			}

			for (int j = 0; j < max_col; j++)
			{
				if (board[i][j] == 0) //숫자가 0일때
					continue;

				count_num[board[i][j]] = make_pair(count_num[board[i][j]].first + 1, count_num[board[i][j]].second);
			}

			sort(count_num.begin(), count_num.end()); //등장횟수, 숫자 우선순위로 정렬

			for (int j = 0; j < count_num.size(); j++)
			{
				if (count_num[j].first == 0) //등장횟수가 0일때
					continue;

				maked_vector.push_back(count_num[j].second);
				maked_vector.push_back(count_num[j].first);
			}

			int maked_vector_size = maked_vector.size();

			temp_max_col = max(temp_max_col, maked_vector_size); //새로 만들어지는 열 중 가장 긴 열의 길이를 구한다

			if (temp_max_col > 100) //새로 만들어지는 열의 길이가 100보다 길어질때
				temp_max_col = 100;

			for (int j = 0; j < 100; j++)
			{
				if (j >= maked_vector.size())
					board[i][j] = 0; //maked_vector 이외의 수는 0으로 표현
				else
					board[i][j] = maked_vector[j];
			}
		}
		max_col = temp_max_col; //max_col을 새로 만들어지는 열중 가장 긴것으로 업데이트
	}

	else
	{
		int temp_max_row = -1;
		for (int i = 0; i < max_col; i++)
		{
			vector<pair<int, int>> count_num(101);
			vector<int> maked_vector;
			
			for (int j = 0; j < 101; j++)
			{
				count_num[j] = make_pair(0, j);
			}

			for (int j = 0; j < max_row; j++)
			{
				if (board[j][i] == 0)
					continue;

				count_num[board[j][i]] = make_pair(count_num[board[j][i]].first + 1, count_num[board[j][i]].second);
			}

			sort(count_num.begin(), count_num.end());

			for (int j = 0; j < count_num.size(); j++)
			{
				if (count_num[j].first == 0)
					continue;

				maked_vector.push_back(count_num[j].second);
				maked_vector.push_back(count_num[j].first);
			}

			int maked_vector_size = maked_vector.size();

			temp_max_row = max(temp_max_row, maked_vector_size);

			if (temp_max_row > 100)
				temp_max_row = 100;

			for (int j = 0; j < 100; j++)
			{
				if (j >= maked_vector.size())
					board[j][i] = 0;
				else
					board[j][i] = maked_vector[j];
			}
		}
		max_row = temp_max_row;
	}
	
	cnt++;

	return Solve(cnt);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> r >> c >> k;

	Pre_board();
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}
	}

	cout << Solve(0);

	return 0;
}