백준 17822 : 원판 돌리기

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

17822번: 원판 돌리기

 

단순 구현문제다. 크기가 50 x 50 밖에 안되므로 시간 걱정하지말고 시원하게 구현하면 된다.

각각의 원판은 사실 인덱스 범위를 벗어날 시 배열의 반대쪽 끝으로 이어진다는 점을 제외하곤 1차원 배열과 동일하다.

 

1. 주어진 명령대로 원판을 회전시킨다.

2. 회전 후 삭제 작업을 수행한다.

   이 때, bfs를 사용하여 동일한 값을 찾아 지워준다.

 

#include <iostream>
#include <queue>

using namespace std;

int n, m;
int board[51][51];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void post_process() {
	int curx, cury, nx, ny, cur_val, cnt = 0;
	bool is_deleted, cur_deleted;
	double sum = 0;
	queue<pair<int, int>> q;

	is_deleted = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!board[i][j]) continue;

			cur_val = board[i][j];
			cur_deleted = 0;
			sum += cur_val;
			++cnt;

			q.emplace(j, i);

			while (!q.empty()) {
				curx = q.front().first, cury = q.front().second;
				q.pop();

				for (int i = 0; i < 4; i++) {
					nx = curx + dx[i], ny = cury + dy[i];
					if (nx <= 0) nx += m;
					else if (nx > m) nx -= m;
					if (ny <= 0 || ny > n || board[ny][nx] != cur_val) continue;

					board[ny][nx] = 0;
					q.emplace(nx, ny);
					is_deleted = 1;
				}
			}

			if (cur_deleted) {
				is_deleted = 1;
				board[i][j] = 0;
			}
		}
	}

	if (!is_deleted) {
		sum /= cnt;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (!board[i][j]) continue;
				if (board[i][j] > sum) --board[i][j];
				else if (board[i][j] < sum) ++board[i][j];
			}
		}
	}
}

void rotate(int x, int d, int k) {
	if (d) k = m - k;

	int idx;
	int tmp[50];
	for (int c = x; c <= n; c += x) {
		for (int i = 1; i <= m; i++) tmp[i] = board[c][i];

		for (int i = 1; i <= m; i++) {
			idx = i + k;
			if (idx > m) idx -= m;
			board[c][idx] = tmp[i];
		}
	}
	
	post_process();
}

void solution() {
	int t, x, d, k, sum = 0;
	cin >> n >> m >> t;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> board[i][j];
		}
	}

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

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			sum += board[i][j];
		}
	}
	cout << sum;
}

int main() { 
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0; 
}

메모리: 2036 kb

시간: 4 ms