[백준] 17822번: 원판 돌리기

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

17822번: 원판 돌리기

나머지 예제 생략

 

문제 이해

원판을 배열로 생각하면 된다. 

• Turn_Plate(): 방향에 맞춰서 해당되는 행을 회전시킨다.
• Erase_Duplicates():
  • 판(pan)의 모든 칸에 대해서 4방향 탐색을 한다. 만약 같은 숫자가 있으면 tmppan 배열에 -1이라고 표시를 해준다.
  • 이때, 열의 끝이 연결되어 있으므로, 열의 범위를 벗어나면 다시 돌아서 행의 반대 끝이 되도록 한다.
    (M --> 0, -1 --> M-1)
  • 탐색을 완료했으면 -1이 되어있는 칸들을 pan에서 지워준다. 
• Add_Sub_Avg() : 평균을 구하고, 평균보다 큰 애들은 -1, 작은 애들은 +1 해준다.
• Get_Answer() : 판의 모든 값을 더한다. 

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 50
#define MAXM 50
int N, M, T;
int pan[MAXN+5][MAXM+5];
int tmppan[MAXN+5][MAXM+5];
int tmp[MAXM + 5];
struct {
	int x, d, k; // x번 원판을 d방향으로 k번 움직임
}cmd[50 + 2];

void Get_Input(void) {
	scanf("%d %d %d", &N, &M, &T);
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &pan[i][j]);
		}
	}
	for (int i = 0; i < T; i++) {
		scanf("%d %d %d", &cmd[i].x, &cmd[i].d, &cmd[i].k);
	}
}

void Turn_Plate(int x, int d, int k) {
	// x의 배수인 원판을 d방향으로 k번 움직임
	int a = (d == 0) ? 1 : -1;
	for(int i = 1; i<=N; i++){
		if (i % x != 0) continue;
		memset(tmp, 0, sizeof(tmp));
		for(int j = 0; j<M; j++){
			tmp[(j + ((a * k)%M) + M) % M] = pan[i][j];
		}
		memcpy(pan[i], tmp, sizeof(tmp));
	}
}

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

int Erase_Duplicates() {
	int cnt = 0;
	// 모든 좌표에 대해서 4방 탐색하면 됨
	memset(tmppan, 0, sizeof(tmppan));
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (pan[i][j] == -1) continue;
			for (int k = 0; k < 4; k++) {
				int ny = dy[k] + i;
				int nx = dx[k] + j;
				if (ny < 1 || ny > N) continue; 
				if (nx == -1) nx = M - 1;
				if (nx == M) nx = 0;
				if (pan[i][j] == pan[ny][nx]) {
					tmppan[i][j] = -1;
					break;
				}
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (tmppan[i][j] == -1) {
				pan[i][j] = -1;
				cnt++;
			}
		}
	}
	return cnt;
}

void Add_Sub_Avg() {
	int sum = 0, cnt = 0;
	double avg;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (pan[i][j] != -1) {
				sum += pan[i][j];
				cnt++;
			}
		}
	}
	avg = (sum * 1.0) / cnt;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (pan[i][j] != -1) {
				if ((double)pan[i][j] > avg) pan[i][j] -= 1;
				else if ((double)pan[i][j] < avg) pan[i][j] += 1;
			}
		}
	}
}

int Get_Answer() {
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (pan[i][j] != -1) {
				sum += pan[i][j];
			}
		}
	}
	return sum;
}

 int main(void) {
	 Get_Input();
	 for (int i = 0; i < T; i++) {
		 Turn_Plate(cmd[i].x, cmd[i].d, cmd[i].k);
		 if(!Erase_Duplicates()) Add_Sub_Avg();
	 }
	 printf("%d", Get_Answer());
	 return 0;
}