백준 17822 원판 돌리기

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

17822번: 원판 돌리기

 

- 브루트포스 + 빡구현 문제이다.

 

- 시간복잡도는 N개의 행에 대해서 rotation을 돌리는 데에 M^2 = O(NM^2) + 모든 칸에 대해서 인접 칸을 살펴야 하므로 O(NM) = O(NM^2)이다. 따라서, 주어진 시간 내에 통과가 가능하다.

 

- 처음 문제를 읽었을 때 어떻게 틀을 잡아야 하는지 망설여질 수 있는데, 삼성 기출이 늘 2차원 배열에서 시작하는 것을 기반으로 해서 생각하면 생각보다 간단하게 주어진 틀을 구현할 수 있음을 알 수 있다. 반지름이 1인 원판부터 시작해서, 북쪽부터 시계방향으로 M개를 순서대로 하여 배열의 한 행을 만들어준다. 이 후, 반지름 2, 3..N에 대해서도 차례대로 진행 해 준다.

 

- rotation은 시계방향의 경우 모든 칸을 한 칸 뒤로, 반시계방향의 경우 모든 칸을 한 칸씩 앞으로 당겨서 구현 해 주면 된다. 해당 작업을 총 k번 해 주면 된다. 필자는 while문 내에서 k번만큼 진행했지만, 시간 단축을 위해선 한 번에 k칸을 이동하는 식으로 구현하는 것이 더 좋을 것이다.

 

- 다음으로, 인접한 칸들을 조사한다. 여기서 이중 for문을 통해 하나하나 조사를 하는데, 만약 특정 칸에 인접한 칸이 서로 수가 같다고 해서 바로 0(문제상의 x)으로 만들어버리면 로직이 망가지기때문에, 0으로 바꿔주어야 하는 칸의 좌표만 따로 will_removed 배열에 true로 표시를 하였다.

 

- 또, 설명을 잘 읽어보면 배열의 좌우 끝의 칸들은 서로 인접하지만, 상하 끝의 칸들은 서로 인접하지 않음을 알 수 있다. 따라서, 이 부분은 따로 처리를 해 주어야 한다. 

 

- is_same 변수를 통해 만약 한 번도 인접한 경우가 없다면 false를 넣고, 이 경우 미리 구했던 평균값을 활용하여 평균보다 작은 값은 +1, 큰 값은 -1을 해 준다. 

 

- 추가로 조금 디버깅에 시간이 걸린 부분은 조금 허무하지만 x의 배수값에 해당하는 반지름을 처리하는 부분이었다. 이 부분에서 x *= 2로 구현을 했다가 계속해서 틀렸었고(나 같은 사람이 많았다), 처음 x값을 temp_x로 저장한 뒤 rotation마다 x += temp_x를 해 주어 해결을 하였다.

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int arr[51][51];
bool will_removed[51][51];
int n, m,t;
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
/*void debugging() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << arr[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}*/
void remove_adjacent() {
	memset(will_removed, false, sizeof(will_removed));
	bool is_same = false;
	int sum = 0; int num = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (arr[i][j] == 0) continue;
			sum += arr[i][j];
			if (arr[i][j] != 0) num++;
			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];
				if (nx < 1 || nx > n) continue;
				if (ny < 1) ny = m; if (ny > m) ny = 1;
				if (arr[i][j] == arr[nx][ny]) {
					will_removed[i][j] = true;
					will_removed[nx][ny] = true;
					is_same = true;
				}
			}
		} 
	}
	if (!is_same) {
		double avg = (float)sum / (float)num;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (arr[i][j] == 0) continue;
				if (arr[i][j] < avg) arr[i][j]++;
				else if (arr[i][j] > avg) arr[i][j]--;
			}
		}
	} else {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (will_removed[i][j]) arr[i][j] = 0;
			}
		}
	}
}
void rotation(int d, int n, int k) {
	while (k--) {
		if (d == 0) {
			int temp = arr[n][m];
			for (int i = m - 1; i >= 1; i--) arr[n][i + 1] = arr[n][i];
			arr[n][1] = temp;
		}
		else {
			int temp = arr[n][1];
			for (int i = 2; i <= m; i++) arr[n][i - 1] = arr[n][i];
			arr[n][m] = temp;
		}
	}
	
}
int main() {
	cin >> n >> m >> t;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	while (t--) {
		int x, d, k;
		cin >> x >> d >> k;
		int temp_x = x;
		while (x<=n) {
			rotation(d, x,k);
			x += temp_x;
		}
		remove_adjacent();
	}
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			sum += arr[i][j];
		}
	}
	cout << sum;
	return 0;
}