백준 17140 - 이차원 배열과 연산

문제링크

• 백준 17140

문제설명

• 크기가 3x3 인 배열 A가 주어진다. 배열의 인덱스는 (1,1) 부터 시작한다.
• 1초가 지날때마다 다음과 같이 두가지 연산 중 하나가 적용된다.
  • R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 >= 열의 개수인 경우에 적용
  • C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용
• 정렬 연산은 다음과 같다.
  • 한 행 혹은 열에 있는 수들 중 등장 횟수가 적은 순서대로 정렬하고, 등장 횟수가 같다면 작은 숫자부터 정렬한다.
  • 모든 행 혹은 열에 대해서 정렬했을 때, 길이가 최대인 곳에 맞추어야 하고 빈칸은 0으로 채운다.
• r,c,k 가 주어졌을 때 A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구하라

문제접근

• 벡터 컨테이너를 적용한 인접리스트를 활용하여 행에 속한 데이터와 열에 속한 데이터를 구분한다.
  • rowList, colList
• 2차원 배열을 선언해서 i번째 행 혹은 열에 등장한 수들의 개수를 저장할 수 있도록 한다.
  • countRowTable, countColTable
• R연산은 열의 길이를 증가시키고, C연산은 행의 길이를 증가시킨다.
  • R연산을 해서 배열을 바꾸고 나면 colList 도 반드시 바꿔줘야 한다.
  • C연산을 해서 배열을 바꾸고 나면 rowList 도 반드시 바꿔줘야 한다.
• 각 행 혹은 열에 연산이 적용되고 나면 countTable 도 반드시 갱신해줘야 한다.

구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

int row, col, k;
int rowNum = 3, colNum = 3;
vector<int> rowList[100];
vector<int> colList[100];
int countRowTable[100][101]; // countRowTable[idx][num] 은 idx번 rowList 배열의 num 이 등장한 횟수
int countColTable[100][101];

// rowNum >= colNum 인 경우
void operatorR() {
	vector<pair<int, int>> list;
	bool checked[101];
	int num, cnt;
	for (int r = 0; r < rowNum; r++) {
		memset(checked, false, sizeof(checked));
		list.clear();
		for (int i = 0; i < rowList[r].size(); i++) {
			num = rowList[r][i];
			cnt = countRowTable[r][num];
			if (num == 0) continue;
			if (checked[num]) continue;
			checked[num] = true;
			list.push_back(make_pair(cnt, num));
		}
		// 정렬 - first 부터 비교해서 오름차순
		sort(list.begin(), list.end());
		
		// update rowList
		memset(countRowTable[r], 0, sizeof(countRowTable[r])); // 반드시 해당하는 행에서만!
		rowList[r].clear();
		for (int i = 0; i < list.size(); i++) {
			rowList[r].push_back(list[i].second);
			rowList[r].push_back(list[i].first);
			countRowTable[r][list[i].second]++;
			countRowTable[r][list[i].first]++;
		}
		colNum = max(colNum, (int)rowList[r].size());
		while (colNum > 100) {
			rowList[r].pop_back();
			colNum--;
		}
	}

	// 0으로 빈칸 채우기
	for (int r = 0; r < rowNum; r++) {
		int cnt = rowList[r].size();
		while (cnt < colNum) {
			rowList[r].push_back(0);
			cnt++;
		}
	}
	// printRowList();

	// update colList
	memset(countColTable, 0, sizeof(countColTable)); // 모든 열에 대해서 갱신!
	for (int c = 0; c < colNum; c++) {
		colList[c].clear();
		for (int r = 0; r < rowNum; r++) {
			colList[c].push_back(rowList[r][c]);
			countColTable[c][rowList[r][c]]++;
		}
	}
	// printColList();
}

void operatorC() {
	vector<pair<int, int>> list;
	bool checked[101];
	int num, cnt;
	for (int c = 0; c < colNum; c++) {
		memset(checked, false, sizeof(checked));
		list.clear();
		for (int i = 0; i < colList[c].size(); i++) {
			num = colList[c][i];
			cnt = countColTable[c][num];
			if (num == 0) continue;
			if (checked[num]) continue;
			checked[num] = true;
			list.push_back(make_pair(cnt, num));
		}
		// 정렬 - first 부터 비교해서 오름차순
		sort(list.begin(), list.end());

		// update colList
		memset(countColTable[c], 0, sizeof(countColTable[c]));
		colList[c].clear();
		for (int i = 0; i < list.size(); i++) {
			colList[c].push_back(list[i].second);
			colList[c].push_back(list[i].first);
			countColTable[c][list[i].second]++;
			countColTable[c][list[i].first]++;
		}
		rowNum = max(rowNum, (int)colList[c].size());
		while (rowNum > 100) {
			colList[c].pop_back();
			rowNum--;
		}
	}

	// 0으로 빈칸 채우기
	for (int c = 0; c < colNum; c++) {
		int cnt = colList[c].size();
		while (cnt < rowNum) {
			colList[c].push_back(0);
			cnt++;
		}
	}
	// printColList();

	// update rowList
	memset(countRowTable, 0, sizeof(countRowTable));
	for (int r = 0; r < rowNum; r++) {
		rowList[r].clear();
		for (int c = 0; c < colNum; c++) {
			rowList[r].push_back(colList[c][r]);
			countRowTable[r][colList[c][r]]++;
		}
	}
	// printRowList();
}

void setOperate() {
	for (int i = 0; i <= 100; i++) {
		// printRowList();
		if (rowNum >= row && colNum >= col) {
			if (rowList[row - 1][col - 1] == k) {
				printf("%d\n", i);
				return;
			}
		}
		if (rowNum >= colNum) {
			operatorR();
		}
		else {
			operatorC();
		}
	}
	printf("-1\n");
	return;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	scanf("%d %d %d", &row, &col, &k);

	memset(countRowTable, 0, sizeof(countRowTable));
	memset(countColTable, 0, sizeof(countColTable));
	int ele;
	for (int r = 0; r < 3; r++) {
		for (int c = 0; c < 3; c++) {
			scanf("%d", &ele);
			rowList[r].push_back(ele);
			colList[c].push_back(ele);
			countRowTable[r][ele]++;
			countColTable[c][ele]++;
		}
	}
	setOperate();
}