[백준][C++] 17822: 원판 돌리기

문제 링크: https://www.acmicpc.net/problem/17822

 

순도 100% 구현 문제입니다. 요새들어 삼성 sw 역량테스트 기출을 좀 풀어보고 있는데 구현 & 시뮬레이션 문제가 엄청 많네요. '이정도는 구현할 줄 알아야 부려먹을 수 있다'라는 걸까요? 암튼 뭐 그렇습니다. 솔직히 풀면서 재미도 별로 없고 힘만 든다는 생각이..

 

이 문제 어렵지는 않습니다. 문제 입력 그대로 배열에 넣고, 회전은 적당히 구현하시거나 std::rotate 쓰면 되고요, 중복된 수 지울 때는 배열 모든 칸에 대해 bfs를 돌리면 됩니다.

 

구현하면서 신경써야 할 점이 좀 있습니다.

• 배열 x축 끝에서 끝으로 가는건 항상 되지만, 배열 y축 n-1에서 0으로 가는건 안됨
  • n==2일때는 예외처리 해주셔야 합니다. 안그러면 94%에서 틀렸습니다가 나옵니다 (경험 有)
• 중복된 수가 없을 때 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더해줘야 하는데, 평균이랑 같은 수는 더하거나 빼지 않습니다 (역시 경험 有)

 

예제 입출력이 정말 자세히 나와있기 때문에 뭐 .,. 틀려도 디버깅은 어렵지 않습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

const int INF = 987654321;
const int REMOVED = -1;
const int DIR[][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

int n, m, t;	//n: 원판 수, m: 원판에 있는 숫자 갯수, t: 회전 수
int board[50][50];	// [원판 순서][숫자]
bool visited[50][50];


bool dfs(int y, int x) {
	if (visited[y][x] || board[y][x]==REMOVED)
		return false;

	// 중복된거 있으면 true 반환
	bool duplicated = false;
	const int& val = board[y][x];

	queue<pair<int, int> > q;
	q.push(make_pair(y, x));
	visited[y][x] = true;

	while (!q.empty()) {
		auto curr_y = q.front().first;
		auto curr_x = q.front().second;
		q.pop();

		if ((curr_y!=y || curr_x!=x) && val == board[curr_y][curr_x]) {
			duplicated = true;
			board[curr_y][curr_x] = REMOVED;
		}

		//next
		for (int i = 0; i < 4; ++i) {
			auto next_y = (curr_y + n + DIR[i][0]) % n;
			auto next_x = (curr_x + m + DIR[i][1]) % m;

			if (n>2 && ((curr_y==0 && next_y==n-1) || (curr_y == n - 1 && next_y == 0)))	//첫번째, 마지막 원판끼리는 X. n==2만 예외
				continue;

			if (!visited[next_y][next_x] && board[next_y][next_x] == val) {
				q.push(make_pair(next_y, next_x));
				visited[next_y][next_x] = true;
			}
		}
	}

	if (duplicated)
		board[y][x] = REMOVED;

	return duplicated;
}

bool remove_duplicate() {
	memset(visited, 0, sizeof(visited));

	bool removed = false;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			if (dfs(i, j))
				removed = true;

	return removed;
}

void update_board() {
	double avg;
	int sum = 0, cnt = 0;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (board[i][j] != REMOVED) {
				++cnt;
				sum += board[i][j];
			}
		}
	}

	if (!cnt)
		return;

	avg = sum / (double)cnt;
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (board[i][j] != REMOVED) {
				if (board[i][j] > avg)
					--board[i][j];
				else if (board[i][j] < avg)
					++board[i][j];
			}
		}
	}
}

int sum() {
	int ret = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			if (board[i][j] != REMOVED)
				ret += board[i][j];
	return ret;
}

//void print() {
//	cout << "---\n";
//	for (int i = 0; i < n; ++i) {
//		for (int j = 0; j < m; ++j) {
//			cout << board[i][j] << ' ';
//		}
//		cout << '\n';
//	}
//}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	cin >> n >> m >> t;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> board[i][j];
		}
	}

	int x, d, k;	//회전
	for (int i = 0; i < t; ++i) {
		cin >> x >> d >> k;
		for (int j = x; j <= n; j += x) {
			std::rotate(board[j-1], board[j-1]+(d==0?m-k:k), board[j-1]+m);
		}
		if (!remove_duplicate()) {
			update_board();
		}
		//print();
	}
	
	cout << sum();

	

	return 0;
}