[백준] 17822번 원판 돌리기

링크

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

17822번: 원판 돌리기

풀이

 

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구하는 문제이다.

 

이 문제는 원판을 돌리고 비교하고 인접한 숫자가 같으면 지우고 인접한 수가 없으면 평균 계산하여 숫자를 증가 및 감소시키면 되는데

 

저는 원판을 돌릴때 deque를 이용했는데

 

원판에 있는 숫자들 중 가장 위에 있는 원소를 0번째 인덱스로 두고 시계 방향으로 돌게 되면

deque에서 맨 뒤에 있는 원소를 맨 앞으로 가지고 오도록 했고

 

반시계 방향으로 돌게 되면 맨 앞에 있는 숫자가 맨 뒤로 가도록 하였습니다.

 

 

이후 원판의 숫자들에 인접한 숫자들이 같은지 확인하고 같다면 빈 공간으로 만들어주고

 

아니면 원판이 돌지 않았다면 모든 비어있지 않은 숫자들의 합(= sum)과 개수(=cnt)를 구하여

 

각각의 숫자 * (cnt)와 sum을 비교하여 작다면 숫자를 증가, 크다면 숫자를 감소하였습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 500
const int INF = 2000000000;
int BLANK = 22222;
using namespace std;

typedef long long int ll;

deque<int> dq[SIZE];
set<pair<int, int>> visited;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

int N, M, T;
//평균 계산을 하기 위해 숫자를 모두 더해줌
int calc() {
	int sum = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			sum += dq[i][j] != BLANK ? dq[i][j] : 0;
		}
	}
	return sum;
}

//인접한 숫자 확인
void check(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int n_x = x + dx[i], n_y = y + dy[i];

		if (n_x == N || n_x == -1)
			continue;
		n_x = x + dx[i] == -1 ? N - 1 : (x + dx[i]) % N;
		n_y = y + dy[i] == -1 ? M - 1 : (y + dy[i]) % M;

		if (dq[x][y] == dq[n_x][n_y] && dq[x][y] != BLANK) {
			visited.insert(make_pair(n_x, n_y));
			visited.insert(make_pair(x, y));
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M >> T;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int num; cin >> num;
			dq[i].push_back(num);
		}
	}

	for (int t = 0; t < T; t++) {
		int x, d, k; cin >> x >> d >> k;

		//시계 방향
		for (int i = x - 1; i < N; i += x) {
			int t_k = k;
			if (d == 0) {
				while (t_k--) {
					dq[i].push_front(dq[i].back());
					dq[i].pop_back();
				}
			}
			//반시계 방향
			else if (d == 1) {
				while (t_k--) {
					dq[i].push_back(dq[i].front());
					dq[i].pop_front();
				}
			}
		}

		int sum = 0, cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				//빈 공간이면 넘어감
				if (dq[i][j] == BLANK) continue;
				check(i, j);
				if (dq[i][j] != BLANK) {
					sum += dq[i][j]; cnt++;
				}
			}
		}

		//돌리기 완료
		if (!visited.empty()) {
			for (auto it = visited.begin(); it != visited.end(); it++) {
				dq[it->first][it->second] = BLANK;
			}
		}
		else if (visited.empty()) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (dq[i][j] != BLANK) {
						if (dq[i][j]*cnt < sum)
							dq[i][j]++;
						else if (dq[i][j]*cnt > sum)
							dq[i][j]--;
					}
				}
			}
		}


		visited.clear();
	}

	cout << calc();

}