백준 17822 - 원판 돌리기

문제링크

• 백준 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)
• 위 설명을 요약하면 원판 위에 숫자는 (i,1)을 시작으로 (i,2), (i,3) .. (i,M)은 시계방향으로 위치한다. 그리고 모든 원판 위에 숫자는 같은 선에 올려져있다.
• 따라서 원판 데이터는 NxM 크기의 2차원 배열의 형태로 나타낼 수 있으며, table[N][M] 은 N번 원판 위의 M번째 원소를 의미한다.
• 번호가 x의 배수인 원판을 d 방향으로 k 칸 회전시킨다.
  • d가 0인 경우 시계 방향, 1인 경우 반시계 방향이다.
• 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
  • 두 수가 인접한다는 의미는 같은 원판에 있으면서 좌우에 위치해있거나, 다른 원판과 같은 선에 놓인 두 숫자를 의미한다고 생각하면 된다.
• 인접하면서 같은 수가 있다면 모두 지운다.
• 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

문제접근

• 원판 데이터를 2차원 배열의 형태로 관리한다.
• 삭제한 원소는 0으로 표현한다.
• 원판 위에 모든 숫자가 0인 원판은 회전할 의미가 없다. 따라서, 회전 로직 적용 전에 미리 파악할 수 있도록 한다.
• 번호가 x의 배수인 원판들만 시계 혹은 반시계 방향으로 k칸 만큼 회전한다.
  • k칸 이동 후 인덱스 계산에 주의할 것
• 삭제할 원소를 찾는다.
  • 회전한 원판만이 아니라 모든 원판에 대해서 적용해야 한다.
  • 삭제되어야 하는 원소는 0으로 설정한다.
• 삭제할 원소가 없다면 평균보다 작은 값은 1을 빼고, 큰 값은 1을 더해준다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;

typedef struct _rot {
	int x, d, k;
} Rot;

int N, M, T;
// x의 배수인 원판을 d방향으로 k칸 회전시킨다.
vector<Rot> rotInfo;
int table[51][51]; // 원판에 적힌 수는 시계 방향으로 자리함

// r번 원판 위에 숫자가 모두 0인지 확인
bool checkValid(int r) {
	for (int c = 1; c <= M; c++) {
		if (table[r][c] != 0) return true;
	}
	return false;
}

void removeNumber() {
	bool removed[51][51];
	memset(removed, false, sizeof(removed));

	// 같은 원에 있는 경우
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c < M; c++) {
			if (table[r][c] == 0) continue;
			if (table[r][c] == table[r][c + 1]) {
				removed[r][c] = true;
				removed[r][c + 1] = true;
			}
		}
		if (table[r][1] == 0) continue;
		if (table[r][1] == table[r][M]) {
			removed[r][1] = true;
			removed[r][M] = true;
		}
	}
	
	// 같은 선에 있는 경우
	for (int c = 1; c <= M; c++) {
		for (int r = 1; r < N; r++) {
			if (table[r][c] == 0) continue;
			if (table[r][c] == table[r + 1][c]) {
				removed[r][c] = true;
				removed[r + 1][c] = true;
			}
		}
	}

	// 숫자 제거
	bool flag = false;
	int sum = 0;
	int cnt = 0;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= M; c++) {
			if (table[r][c] == 0) continue;
			if (removed[r][c]) {
				table[r][c] = 0;
				flag = true;
			}
			else {
				sum += table[r][c];
				cnt++;
			}
		}
	}

	// 지운 수가 없는 경우 평균 보다 작은 수는 +1, 큰 수는 -1
	float avg = (float)sum / cnt;
	if (flag == false) {
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= M; c++) {
				if (table[r][c] == 0) continue;
				if (table[r][c] < avg) table[r][c]++;
				else if (table[r][c] > avg) table[r][c]--;
			}
		}
	}
	// printTable();
}

void rotateCircle(int x, int d, int k) {
	int ntable[51][51];
	memcpy(ntable, table, sizeof(table));
	// d=0 : 시계 방향, d=1: 반시계 방향
	// k칸 회전, 번호가 x의 배수인 원판
	if (d == 0) {
		for (int r = x; r <= N; r += x) {
			if (checkValid(r)==false) continue;
			for (int c = 1; c <= M; c++) {
				int nextC = c + k;
				if (nextC > M) nextC -= M;
				ntable[r][nextC] = table[r][c];
			}
		}
	}
	else if (d == 1) {
		for (int r = x; r <= N; r += x) {
			if (checkValid(r)==false) continue;
			for (int c = 1; c <= M; c++) {
				int nextC = c - k;
				if (nextC <= 0) nextC += M;
				ntable[r][nextC] = table[r][c];
			}
		}
	}
	memcpy(table, ntable, sizeof(table));
	// printTable();
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d %d", &N, &M, &T);

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= M; c++) {
			scanf("%d", &table[r][c]);
		}
	}

	int x, d, k;
	Rot rot;
	for (int i = 0; i < T; i++) {
		scanf("%d %d %d", &x, &d, &k);
		rot = { x,d,k };
		rotInfo.push_back(rot);
	}
	
	for (int i = 0; i < T; i++) {
		rotateCircle(rotInfo[i].x, rotInfo[i].d, rotInfo[i].k);
		removeNumber();
	}

	int ans = 0;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= M; c++)
			ans += table[r][c];
	}
	printf("%d\n", ans);
}