[백준] 17822 - 원판돌리기

17822 백준 원판돌리기

문제

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

아래 그림은 N = 3, M = 4인 경우이다.

원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키지 전과 일치해야 한다.

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
2. 인접하면서 수가 같은 것을 모두 찾는다.
   1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
   2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

예제 입력 1

4 4 1

1 1 2 3

5 2 4 2

3 1 3 5

2 1 3 2

2 0 1

예제 출력 1

30

원판의 초기 상태는 다음과 같다.

x1 = 2, d1 = 0, k1 = 1 2번, 4번 원판을 시계 방향으로 1칸 돌린 후

인접하면서 수가 같은 것을 모두 지운 후

입력

#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<algorithm>
using namespace std;

int N, M, T;

int CNT;
int SUM;

const int INF_MIN = INT32_MIN;

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

void changeAdjacent(vector<deque<int>>& circle, int order, int pos, bool& isAdj) {
	vector<vector<bool>> visited(N);
	for (int i = 0; i < N; i++) 
		visited[i].resize(M);

	queue<pair<int, int>> que;
	que.push({ order, pos });
	bool isChange = false;

	visited[order][pos] = true;
	int cmpNum = circle[order][pos];

	while (!que.empty()) {
		int popOrder = que.front().first;
		int popPos = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int newOrder = popOrder + dy[i];
			int newPos = popPos + dx[i];

			if (newOrder < 0 || newOrder >= N) continue;
			newPos = newPos < 0 ? M - 1 : newPos >= M ? 0 : newPos;

			if (visited[newOrder][newPos] == false && circle[newOrder][newPos] == cmpNum) {
				visited[newOrder][newPos] = true;
				que.push({ newOrder, newPos });

				SUM -= circle[newOrder][newPos];
				circle[newOrder][newPos] = INF_MIN;
				
				CNT--;
				isChange = true;
			}
		}		
	}

	if (isChange == true) {
		SUM -= circle[order][pos];
		CNT--;
		circle[order][pos] = INF_MIN;
		isAdj = true;
	}		
}

void checkAdjacent(vector<deque<int>>& circle, bool& isAdj) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if(circle[i][j] != INF_MIN)
				changeAdjacent(circle, i, j, isAdj);
		}
	}
}

void avgPlusMinus(vector<deque<int>>& circle, double avg) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (circle[i][j] != INF_MIN) {
				if (circle[i][j] > avg) {
					SUM -= 1;
					circle[i][j] -= 1;
				}
				else if (circle[i][j] < avg) {
					SUM += 1;
					circle[i][j] += 1;
				}
					
			}
		}
	}
}

int main() {
	/* INIT Phase */
	cin >> N >> M >> T;

	vector<deque<int>> circle(N);

	int number;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> number;
			SUM += number;
			CNT++;
			circle[i].push_back(number);
		}
	}
	/* SOLVE Phase */
	/* x의 배수 원판을 d의 방향으로(0은 시계, 1은 반시계) k번 회전*/
	int x; bool d; int k;
	while (T--) {
		cin >> x >> d >> k;
		for (int i = 1; i * x <= N; i++) {
			int multiple_x = i * x - 1;
			for(int rotate = 0; rotate < k; rotate++) {
				if (d == 0) {
					int tmp = circle[multiple_x].back();
					circle[multiple_x].pop_back();
					circle[multiple_x].push_front(tmp);
				}
				else {
					int tmp = circle[multiple_x].front();
					circle[multiple_x].pop_front();
					circle[multiple_x].push_back(tmp);
				}

			}
		}
		bool isAdjacent = false;
		checkAdjacent(circle, isAdjacent);
		if (isAdjacent == false) {
			double avg;
			if (CNT != 0)
				avg = (double)SUM / CNT;
			else avg = 0;

			avgPlusMinus(circle, avg);
		}
	}

	/* PRINT Phase */
	cout << SUM;

	return 0;
}

15920830

rational331

17822

원판 돌리기

맞았습니다!!

2124KB

344ms

C++17

3383

사실 문제 자체를 덱으로 회전을 시키고, BFS를 통해 근접한 원소를 삭제하는 방식으로 구현하려 했으나, 시간이 344ms나 걸려 깜짝 놀랐다. 알고보니 모든 원소에서 BFS를 수행하여 결국 시간복잡도 O(N^4)이 걸리게 된다.

---

이를 최적화 시킬 방법으로 단순히 배열을 순회 하면서 양옆으로 겹치는 것이 있는지, 위아래로 겹치는 것이 있는지 확인하면서 O(N^2)으로 최적화를 진행하였다.

#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<algorithm>
using namespace std;

int N, M, T;

int SUM;
int CNT;

const int INF_MIN = INT32_MIN;

void checkAdjacent(vector<deque<int>>& circle) {
	vector<vector<bool>> isDel(N);
	for (int i = 0; i < N; i++) 
		isDel[i].resize(M);

	bool isChange = false;

	/* 1. 양 옆으로 확인 */
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M - 1; j++) {
			if (circle[i][j] != INF_MIN && 
            		circle[i][j + 1] != INF_MIN && 
            		circle[i][j] == circle[i][j + 1]) {
				isDel[i][j] = true;
				isDel[i][j + 1] = true;
				isChange = true;
			}
		}
		if (circle[i][0] != INF_MIN && 
        	circle[i][M - 1] != INF_MIN && 
        	circle[i][0] == circle[i][M - 1]) {
			isDel[i][0] = true;
			isDel[i][M - 1] = true;
			isChange = true;
		}
	}
	/* 2. 위 아래로 확인 */
	for (int j = 0; j < M; j++) {
		for (int i = 0; i < N - 1; i++) {
			if (circle[i][j] != INF_MIN && 
            		circle[i + 1][j] != INF_MIN && 
            		circle[i][j] == circle[i + 1][j]) {
				isDel[i][j] = true;
				isDel[i + 1][j] = true;
				isChange = true;
			}
		}
	}

	if (isChange == true) {
		/* 3. 변경되었으면 삭제하기 */
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (circle[i][j] != INF_MIN && isDel[i][j] == true) {
					SUM -= circle[i][j];
					CNT--;
					circle[i][j] = INF_MIN;
				}
			}
		}
	}
	else {
		/* 4. 변경 안됬으면 평균 구하고 +1, -1과정 거치기 */
		double AVG = (double)SUM / CNT;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (circle[i][j] != INF_MIN) {
					if (circle[i][j] > AVG) {
						circle[i][j] -= 1;
						SUM--;
					}
					else if(circle[i][j] < AVG) {
						circle[i][j] += 1;
						SUM++;
					}
				}
			}
		}
	}
}

int main() {
	/* INIT Phase */
	cin >> N >> M >> T;

	vector<deque<int>> circle(N);

	int number;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> number;
			SUM += number;
			CNT++;
			circle[i].push_back(number);
		}
	}
	
	/* SOLVE Phase */
	/* x의 배수 원판을 d의 방향으로(0은 시계, 1은 반시계) k번 회전*/
	int x; bool d; int k;
	while (T--) {
		cin >> x >> d >> k;
		for (int i = 1; i * x <= N; i++) {
			int multiple_x = i * x - 1;
			for (int rotate = 0; rotate < k; rotate++) {
				if (d == 0) {
					int tmp = circle[multiple_x].back();
					circle[multiple_x].pop_back();
					circle[multiple_x].push_front(tmp);
				}
				else {
					int tmp = circle[multiple_x].front();
					circle[multiple_x].pop_front();
					circle[multiple_x].push_back(tmp);
				}

			}
		}
		checkAdjacent(circle);	
	}

	/* PRINT Phase */
	cout << SUM;

	return 0;
}