백준 17140 (이차원 배열과 연산)

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

해당 문제는 간단한 구현 문제이다.

Y, X, K 값이 주어지며 배열의 Y, X 번째 요소가 K가 되는 경우를 찾는 문제이다.

3 * 3 에 해당하는 2차원 배열에 각 수가 주어지며 다음과 같은 조건일 때 배열이 변화한다.

Y 축의 값과 X축의 값을 비교했을 때 Y 축의 값이 X 보다 크거나 같다면 X축의 값을들 비교한다.

위의 경우가 아닌경우 Y축의 값들을 비교한다.

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

using namespace std;
int my = 3, mx = 3;
int map[100][100];
struct Node{
	int overLap;
	int num;
};

bool comps(Node a, Node b){
	if (a.overLap < b.overLap) return true;
	else if (a.overLap == b.overLap){
		if (a.num < b.num) return true;
		else return false;
	}
	else return false;
}

void checkR(){

	int cpMap[100][100] = { 0 };
	int tmpY = 0;
	int maxx = 0;
	
    // X 축을 고정으로 Y축을 변경해가며 Y축의 값들을 정렬한다.
	for (int x = 0; x < mx; ++x){
		int idx = 0;
		vector<int> idxList;
		vector<Node> result;
		Node nodeList[150] = { 0 };

		for (int y = 0; y < my; ++y){
			if (map[y][x] == 0) continue;
            // 만약 배열의 현재 요소가 0 보다 크면서 한번도 나오지 않은 숫자일경우
			if (nodeList[map[y][x]].overLap == 0){
				idxList.push_back(map[y][x]);
				nodeList[map[y][x]].num = map[y][x];
			};
            // 배열의 숫자에 해당하는 인덱스의 중첩 값 ++
			nodeList[map[y][x]].overLap++;
		}

		int n = idxList.size();

		for (int j = 0; j < n; ++j){
			result.push_back(nodeList[idxList[j]]);
		}
		sort(result.begin(), result.end(), comps);

		for (int j = 0; j < n; ++j){
			if (result[j].num == 0) break;
			if (idx >= 100) break;
			if (idx + 2 > tmpY) tmpY = idx + 2;
			cpMap[idx][x] = result[j].num;
			cpMap[idx + 1][x] = result[j].overLap;
			idx += 2;
		}
	}
	memcpy(map, cpMap, 4 * 100 * 100);
	my = tmpY;
}

void checkC(){
	int cpMap[100][100] = { 0 };
	int tmpX = 0;
	int maxx = 0;
	for (int i = 0; i < my; ++i){
		int idx = 0;
		vector<int> idxList;
		vector<Node> result;
		Node nodeList[150] = { 0 };

		for (int j = 0; j < mx; ++j){
			if (map[i][j] == 0) continue;
			if (nodeList[map[i][j]].overLap == 0){ 
				idxList.push_back(map[i][j]);
				nodeList[map[i][j]].num = map[i][j];
			};
			nodeList[map[i][j]].overLap++;
		}

		int n = idxList.size();

		for (int j = 0; j < n; ++j){
			result.push_back(nodeList[idxList[j]]);
		}
		sort(result.begin(), result.end(), comps);
		
		for (int j = 0; j < n; ++j){
			if (result[j].num == 0) break;
			if (idx >= 100) break;
			if (idx + 2 > tmpX) tmpX = idx + 2;
			cpMap[i][idx] = result[j].num;
			cpMap[i][idx + 1] = result[j].overLap;
			idx += 2;
		}
	}
	memcpy(map, cpMap, 4 * 100 * 100);
	mx = tmpX;
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	int ty, tx, k;
	int cnt = 0;

	cin >> ty >> tx >> k;
	ty--; tx--;

	for (int i = 0; i < 3; ++i){
		for (int j = 0; j < 3; ++j){
			cin >> map[i][j];
		}
	}
	
	while (1){
		if (map[ty][tx] >= 100) break;
		if (map[ty][tx] == k) break;
		if (cnt > 100) {
			cnt = -1;
			break;
		}
		if (my >= mx) checkC();
		else if (my < mx) checkR();
		++cnt;
	}
	printf("%d ", cnt);
}