[C/C++] 백준 - 17140번 (시물레이션)

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

17140번: 이차원 배열과 연산

문제

크기가 3×3인 배열 A가 있다. 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가 되기 위한 최소 시간을 구해보자.

입력

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

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

출력

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

 

이 문제를 풀 때 나는 내 코드가 시간초과가 뜰 줄 알았다. 아직 시간복잡도 계산하는 거에 있어 미숙하고 잘 모르기 때문에 

내 코드는 당연히 시간초과가 뜰 줄 알았는데 0ms가 떠서 정말 기분이 좋았다.

 

나는 벡터와 큐를 이용하여 문제를 해결하였다.어떤 연산을 수행해야하는지는 문제 설명에 나와있으므로 각 최대열, 최대행을 저장하는 변수를 선언해서 비교한 후각 연산을 수행하도록 하였다.

 

그리고 각 연산 안에서는 행/열에 들어있는 수를 하나씩 탐색하며 아직 체크하지 않은 변수는 큐에 넣고 visited변수를 통해 큐에 넣은 수는 방문표시를 해주었다. 그리고 방문처리된 수의 개수는 count변수를 통해 개수를 세어주고, 탐색이 모두 끝나면큐에서 꺼내 그 수에 해당하는 개수와 함께 pair형태의 벡터에 넣어주었다.

 

위 과정으로 초기화를 하며 원하는 위치에 값이 오면 while무한반복문을 빠져나와 답을 출력하고, 100번 이상 반복하면 -1을 출력하고 바로 프로그램을 끝내는 방식으로 작성하였다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define MAX_SIZE 155
#define swap(type,x,y) do{type t=x;x=y;y=t;} while(0)

using namespace std;

// 1초가 지날때마다 수행
// R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
// C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
// 각각의 수가 몇 번 나왔는지 알아야하고, 수의 등장 횟수가 커지는 순.
// 그러한 것이 여러가지면 수가 커지는 순으로 정렬

int adj[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE];
int R, C, K;
int max_r, max_c;

deque<pair<int, int>> v;
queue<int> q;

void input() {
	scanf("%d %d %d", &R, &C, &K);
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			scanf("%d", &adj[i][j]);
		}
	}
	max_r = max_c = 3;
}

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;
}

void R_replace(int idx) {
	int ps = 1;
	memset(adj[idx], 0, sizeof(adj[idx]));
	while (!v.empty()) {
		int frt = v.front().first;
		int scd = v.front().second;
		v.pop_front();

		adj[idx][ps++] = frt;
		adj[idx][ps++] = scd;
	}
	if (ps - 1 > max_c) {
		max_c = ps - 1;
	}
}

void R_cal() {
	int count[105] = { 0, };
	for (int i = 1; i <= max_r; i++) {
		memset(visited, false, sizeof(visited));
		memset(count, 0, sizeof(count));
		for (int j = 1; j <= max_c; j++) {
			if (adj[i][j] != 0 && visited[adj[i][j]] == false) {
				visited[adj[i][j]] = true;
				q.push(adj[i][j]);
				count[adj[i][j]]++;
			}
			else if (adj[i][j] != 0 && visited[adj[i][j]] == true) {
				count[adj[i][j]]++;
			}
			else if (adj[i][j] == 0) continue;
		}
		while (!q.empty()) {
			int idx = q.front();
			q.pop();
			v.push_back({ idx, count[idx] });
		}
		sort(v.begin(), v.end(), compare);
		R_replace(i);
		v.clear();
	}
}

void C_replace(int idx) {
	int ps = 1;
	for (int i = 1; i <= max_c; i++) {
		if (adj[i][idx] == 0) continue;
		adj[i][idx] = 0;
	}
	while (!v.empty()) {
		int frt = v.front().first;
		int scd = v.front().second;
		v.pop_front();

		adj[ps++][idx] = frt;
		adj[ps++][idx] = scd;
	}
	if (ps - 1 > max_r) {
		max_r = ps - 1;
	}
}

void C_cal() {
	int count[105] = { 0, };
	for (int i = 1; i <= max_c; i++) {
		memset(visited, false, sizeof(visited));
		memset(count, 0, sizeof(count));
		for (int j = 1; j <= max_r; j++) {
			if (adj[j][i] != 0 && visited[adj[j][i]] == false) {
				visited[adj[j][i]] = true;
				q.push(adj[j][i]);
				count[adj[j][i]]++;
			}
			else if (adj[j][i] != 0 && visited[adj[j][i]] == true) {
				count[adj[j][i]]++;
			}
			else if (adj[j][i] == 0) continue;
		}
		while (!q.empty()) {
			int idx = q.front();
			q.pop();
			v.push_back({ idx, count[idx] });
		}
		sort(v.begin(), v.end(), compare);
		C_replace(i);
		v.clear();
	}
}

void Print(int ps) {
	printf("\n\n\n");
	printf("Current's time : %d\n", ps);
	printf("Current -> Wide : %d, Faith : %d\n", max_c, max_r);
	for (int i = 1; i <= max_r; i++) {
		for (int j = 1; j <= max_c; j++) {
			printf("%d ", adj[i][j]);
		}
		printf("\n");
	}
}

int Solve() {
	int past = 0;
	while (1) {
		if (adj[R][C] == K) break;
		if (past >= 100) {
			printf("-1\n");
			return 0;
		}
		if (past == 0) {
			R_cal();
		}
		else {
			if (max_r >= max_c) {
				R_cal();
			}
			else {
				C_cal();
			}
		}
		past++;
		//Print(past);
	}
	printf("%d\n", past);

	return 1;
}

int main() {
	input();
	Solve();

	return 0;
}