[C++] BOJ(백준) 17822 원판 돌리기

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

 

난이도를 확 높인 골2 구현 문제다.

 

나름 유명한 문제고, 이전에도 문제 찾다가 종종 본 적이 있었는데 딱 봐도 귀찮아서 안했었다.

근데 오랜만에 잡으니까 근자감으로 이 정도는 껌일 것 같아서 시도 했더니 껌이었다ㅋ

 

우선 원판 회전을 위해 배열 대신 벡터를 사용했다.

방향을 주의하여 한쪽 끝의 값을 저장하고 삭제한 뒤 반대쪽 끝에 값을 삽입했다.

 

이후 이웃한 값이 같은 값인지를 판단해야 한다.

간단하게 머리로 시뮬레이션을 돌려봤더니 밖에서부터 하든 안에서부터 하든 문제가 발생했다.

예를 들면 원판의 값이 1 1 1인 경우 처음 두 개의 1 1 이 같아 0 0 1로 바꿔버리면 마지막 1은 같은데도 불구하고 무시된다.

 

그래서 찾은 방법은 원 배열은 살려두고 이웃한 값이 같은지 확인하는 bool 배열을 하나 더 만들어 체크했다.

원판의 모든 위치에 대해 검사한 후 원판 전체를 한 번 더 탐색하면서 bool 배열의 값이 참인 경우 0으로 바꾼다.

 

탐색을 마쳤을 때 같은 값이 없다면 평균 값을 이용한 계산을 해야한다.

같은 값의 여부를 확인하기 위해서 위 search 함수에서 bool형 리턴을 이용했다.

bool 배열의 참이 있어 원판 배열의 값을 0으로 바꿀 때 반환할 변수의 값도 true로 바꿔준다.

 

평균 값 계산은 말 그대로 원판 값들의 평균을 계산하고 대소 비교를 하면 된다.

 

이 때 평균보다 클 때, 작을 때의 경우만 제시되어 있어서 같은 경우는 어쩌지... 하고 질문 게시판을 봤는데

똑같은 질문이 있었고 아무것도 안하면 된단다...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

작성한 코드는 아래와 같다.

단계별로 모듈화도 진행했는데, rotate를 호출하는 과정도 함수 안에 포함했으면 좋았을 걸 싶다.

 

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

int n, m, t;
vector<int> one[51];
int arr[50];
bool check[51][51];

void rotate(int x, int d, int k) {
	if (!d) {
		while (k--) {
			int tmp = one[x][m - 1];
			one[x].erase(one[x].end() - 1);
			one[x].insert(one[x].begin(), tmp);
		}
	}
	else {
		while(k--) {
			int tmp = one[x][0];
			one[x].erase(one[x].begin());
			one[x].push_back(tmp);
		}
	}
}

int dr[4] = { 0, 1, 0, -1 };
int dc[4] = { 1, 0, -1, 0 };
bool search() {

	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++) check[i][j] = false;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 4; k++) {
				int rr = i + dr[k];
				int cc = j + dc[k];

				if (rr < 1 || rr > n || cc < 0 || cc >= m) continue;
				if (one[i][j] == 0) continue;

				if (one[rr][cc] == one[i][j]) {
					check[rr][cc] = true;
					check[i][j] = true;
				}
			}
		}
		if (one[i][0] == one[i][m - 1] && one[i][0] != 0) {
			check[i][0] = true;
			check[i][m - 1] = true;
		}
	}

	bool c = false;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++)
			if (check[i][j]) {
				c = true;
				one[i][j] = 0;
			}
	}

	return c;
}

void count() {
	int cnt = 0;
	double sum = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++) {
			if (one[i][j]) cnt++;
			sum += one[i][j];
		}

	sum /= cnt;

	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++) {
			if (one[i][j] == 0) continue;
			if (one[i][j] > sum) one[i][j] --;
			else if (one[i][j] < sum) one[i][j]++;
		}
}

int main() {

	cin >> n >> m >> t;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int a;	cin >> a;
			one[i + 1].push_back(a);
		}
	}

	while (t--) {
		int x, d, k;
		cin >> x >> d >> k;

		// 회전하기
		int tmp = 1;
		while (x * tmp <= n) {
			rotate(x * tmp, d, k);
			tmp++;
		}

		// 인접하는 수 찾기
		bool c = search();

		// 평균 처리
		if (!c) count();
	}

	int res = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) 
			res += one[i + 1][j];

	cout << res;
}