[ 백준 - 17822번 / 시뮬레이션 ] 원판 돌리기 (삼성 SW)

1. 문제

---

 

17822번: 원판 돌리기

문제

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 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번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

다음 그림은 원판을 회전시킨 예시이다.

1번 원판을 시계 방향으로 1칸 회전	2, 3번 원판을 반시계 방향으로 3칸 회전	1, 3번 원판을 시계 방향으로 2칸 회전

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

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

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

입력

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.

다음 T개의 줄에 xi, di, ki가 주어진다.

출력

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

제한

• 2 ≤ N, M ≤ 50
• 1 ≤ T ≤ 50
• 1 ≤ 원판에 적힌 수 ≤ 1,000
• 2 ≤ xi ≤ N
• 0 ≤ di ≤ 1
• 1 ≤ ki < M

예제 입력 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

 

 

 

 

 

2. 소스코드

---

1회차

 

- 하나의 원판을 하나의 vector에 담고, 그 vector들을 담는 vector로 컨테이너 설정.

- (회전 > 중복 > 평균) 순서대로 구현하였음. 효율적인 측면에서 개선 필요.

- 중복을 체크할때, 좌우상하, 최대거리까지 한번에 고려하고 반영해야함.

- 평균을 계산할때, 강제 형변환이 필수. (문제에 내림하라는 말이 없으므로)

 

- 예상 시간 복잡도

1) 입력 : O(N^2)

2-1) 명령어 수행 : T

2-2) 회전 : O(NM)

2-3) 인접체크 : O(NM)

2-4) 평균계산: O(NM)

2-5) 평균과 비교 : O(NM)

 

합 : O(N^2) + O(T x (NM + NM + NM + NM)) = O(N^2) + O(4TNM) = O(N^2) + O(TNM)

 

#pragma warning (disable : 4996)

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
 
using namespace std;

vector<vector<int>> disks;
queue<tuple<int, int, int>> rotateMethod;
int n, m, T;

void rotateDisk() {

	while (T--)
	{
		auto k = rotateMethod.front();
		int x = get<0>(k);
		int dir = get<1>(k);
		int cntRotate = get<2>(k);
		rotateMethod.pop();
		for (int i = 0; i < disks.size(); i++) {
			//디스크의 번호가 배수라면
			if ((i + 1) % x == 0) {
				//칸수만큼
				for (int j = 0; j < cntRotate; j++) {
					//시계방향 // 뒤에서 빼서 앞에 넣는다.
					if (dir == 0) {
						int temp = disks[i][m - 1];
						disks[i].insert(disks[i].begin(), temp);
						disks[i].pop_back();
					}
					//반시계 방향 // 앞에서 빼서 뒤에 넣는다.
					else {
						int temp = disks[i][0];
						disks[i].push_back(temp);
						disks[i].erase(disks[i].begin(), disks[i].begin() + 1);
					}
				}
			}
		}//end 회전
		// 인접을 체크한다
		// disk 전체를
		bool isAdjacent = false;
		queue <pair<int, int>> delPoint;
		for (int i = 0; i < disks.size(); i++) {
			//그 disk 안에 돌면서
			for (int j = 0; j < m; j++) {
				//중복이다. %연산자를 이용하면 앞/뒤를 이어서 체크 할 수 있다.
				if (disks[i][j % m] == disks[i][(j + 1) % m] and disks[i][j] != 0) {
					delPoint.push({ i,j });
					delPoint.push({ i,(j + 1) % m });
					isAdjacent = true;
				}
				// 다른 disk랑 중복인경우
				if (i - 1 >= 0) {
					if (disks[i - 1][j] == disks[i][j] and disks[i][j] != 0) {
						delPoint.push({ i - 1,j });
						delPoint.push({ i,j });
						isAdjacent = true;
					}
				}
				if (i + 1 < disks.size()) {
					if (disks[i + 1][j] == disks[i][j] and disks[i][j] != 0) {
						delPoint.push({ i + 1,j });
						delPoint.push({ i,j });
						isAdjacent = true;
					}
				}
			}
		}// 중복 체크 end
		while (!delPoint.empty())
		{
			int nx = delPoint.front().first;
			int ny = delPoint.front().second;
			delPoint.pop();
			disks[nx][ny] = 0;
		}
		//중복이 아니라면! disk마다 평균을 구하고! ++ -- 를 해준다
		if (isAdjacent == false) {
			int sum = 0, numcnt = 0;
			for (int i = 0; i < disks.size(); i++) {
				for (int j = 0; j < m; j++) {
					if (disks[i][j] != 0) {
						sum += disks[i][j];
						numcnt++;
					}
				}
			}
			double avg = (double)sum / numcnt;
			// disk 전체를
			for (int i = 0; i < disks.size(); i++) {
				for (int j = 0; j < m; j++) {
					if ((double)disks[i][j] > avg and disks[i][j]!=0)
						disks[i][j]--;
					else if ((double)disks[i][j] < avg and disks[i][j]!=0)
						disks[i][j]++;
				}
			}
		}// 평균 덧샘끝!
	}
}

int main() {
	cin >> n >> m >> T;
	for (int i = 0; i < n; i++) {
		vector<int> temp;
		for (int j = 0; j < m; j++) {
			int num; cin >> num;
			temp.push_back(num);
		}
		disks.push_back(temp);
	}
	for (int i = 0; i < T; i++) {
		int x, dir, cntRotate;
		cin >> x >> dir >> cntRotate;
		rotateMethod.push(make_tuple(x,dir,cntRotate));
	}
	rotateDisk();

	int sum = 0;
	for (int i = 0; i < disks.size(); i++) {
		for (int j = 0; j < m; j++) {
			sum += disks[i][j];
		}
	}
	cout << sum << '\n';

	return 0;
}