[백준 17822] 원판 돌리기 (C++)

문제 링크: https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

[느낀 점]

- 최근에 작성한 코드가 더 깔끔한 느낌

- 이전 코드:  WA 상태에서 고친 코드

- 최근 코드: 함수를 통해 각 수행 부분을 분담 → AC

 

결론: 한번에 제대로 작성하도록 하자

 

1. 주의할 점

- 원판의 숫자에 0만 남아있다면 더 이상 수행하지 않아도 된다

- 원판에는 4개의 숫자가 아닌 M개의 숫자가 써져있다

 

2. 구현

- 원판에 대한 정보를 입력받은 후, 원판을 회전한다. 회전할때엔 한방향으로 통일 시켜서 회전 함수가 더 간단해지도록 한다(반시계 방향으로 3번 회전: 시계 방향으로 M-3번 회전)

- BFS()를 통해 주위에 같은 숫자가 있는지 확인하고 있다면 0으로 만든다

- 0으로 만든 숫자가 없는 경우, 원판에 적힌 숫자의 평균을 구하여 그보다 작은 값은 +1, 큰 값은 -1을 한다 (0은 제외)

- 평균 함수를 수행하기 전에, Allzero() 함수를 통해 BFS() 이후에 원판이 전부 0으로 됐는지 확인하고, 전부 0이라면 이후에 입력 받는 명령어들을 수행하지 않는다

 

//약 10달 전 코드
#include <iostream>
#include <queue>
#include <math.h>
using namespace std;
struct info {
	int x, y, val;
};
info tmp;
int n, m, t;
int arr[51][50];
bool check[51][50], flag;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

void cal() {
	int sum = 0;
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++) {
			if (arr[i][j] != 0) {
				sum += arr[i][j];
				cnt++;
			}
		}
	double avg = (double)sum / cnt;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++) {
			if (arr[i][j] != 0) {
				if (arr[i][j] < avg)	arr[i][j] += 1;
				else if (arr[i][j] > avg)	arr[i][j] -= 1;
			}
		}
}

void bfs(int y, int x) {
	queue<info> q, er;
	check[y][x] = true;
	tmp.x = x;
	tmp.y = y;
	tmp.val = arr[y][x];
	q.push(tmp);
	er.push(tmp);
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		int cv = q.front().val;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int nx = cx + dx[k];
			int ny = cy + dy[k];
			if (nx == -1) nx = m - 1;
			else if (nx == m) nx = 0;
			if (1 <= ny && ny <= n) {
				if (arr[ny][nx] == cv && !check[ny][nx]) {
					check[ny][nx] = true;
					tmp.x = nx;
					tmp.y = ny;
					tmp.val = cv;
					q.push(tmp);
					er.push(tmp);
				}
			}
		}
	}
	if (er.size() > 1) {
		flag = true;
		while (!er.empty()) {
			int cx = er.front().x;
			int cy = er.front().y;
			er.pop();
			arr[cy][cx] = 0;
		}
	}
}


void rot(int lev, int many) {		//시계방향으로만 회전
	for (int k = 0; k < many; k++) {
		int temp = arr[lev][m - 1];
		for (int i = m-1; i > 0; i--) 
			arr[lev][i] = arr[lev][i - 1];		
		arr[lev][0] = temp;
	}
}

bool test() {
	bool tt = true;
	for (int k = 1; k <= n; k++) {
		for (int j = 0; j < m; j++)
			if (arr[k][j] != 0) {
				tt = false;
				break;
			}
		if (!tt) break;
	}
	return tt;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> t;
	for (int i = 1; i <= n; i++) 
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];
	
	bool allzero = false;
	int plate, dir, many;
	for (int i = 0; i < t; i++) {
		cin >> plate >> dir >> many;
		if (allzero) continue;
		if (dir == 1) many = m - many;
		for (int k = plate; k <= n; k += plate)
			rot(k, many);
		flag = false;
		for (int k = 1; k <= n; k++)
			for (int j = 0; j < m; j++)
				check[k][j] = false;
		for (int k = 1; k <= n; k++)
			for (int j = 0; j < m; j++) {
				if (!check[k][j] && arr[k][j] > 0) {
					bfs(k, j);
				}
			}
		allzero = test();			
		if(!allzero && !flag)
			cal();		
	}
	int result = 0;
	for (int k = 1; k <= n; k++) 
		for (int j = 0; j < m; j++) 
			result += arr[k][j];
	cout << result;
	return 0;
}

//=========================================================================

//2021.04.21 코드
#include <iostream>
#include <queue>
using namespace std;
struct info {
	int y, x;
};
info tmp;
int arr[51][51];
bool check[51][51];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int row, col, query, num, dir, k, result = 0;

void bfs() {
	for (int i = 1; i <= row; i++)
		for (int j = 1; j <= col; j++)
			check[i][j] = false;
	bool flag = false;
	for (int i = 1; i <= row; i++)
		for (int j = 1; j <= col; j++) {
			if (!check[i][j] && arr[i][j]>0) {
				check[i][j] = true;
				bool haveSame = false;
				queue<info> q;
				q.push({ i,j});
				int val = arr[i][j];
				while (!q.empty()) {
					int cx = q.front().x;
					int cy = q.front().y;
					q.pop();
					for (int m = 0; m < 4; m++) {
						int nx = cx + dx[m];
						int ny = cy + dy[m];
						if (nx > col) nx = 1;
						else if (nx < 1) nx = col;
						if (ny > 0 && ny <= row && !check[ny][nx] && arr[ny][nx] == val) {
							q.push({ ny,nx });
							check[ny][nx] = true;
							arr[ny][nx] = 0;
							haveSame = true;
						}
					}
				}
				if (haveSame) {
					arr[i][j] = 0;
					flag = true;
				}
			}
		}
	if (!flag) {
		int tot = 0;
		int cnt = 0;
		for (int i = 1; i <= row; i++)
			for (int j = 1; j <= col; j++) {
				tot += arr[i][j];
				if (arr[i][j] > 0) cnt++;
			}

		for (int i = 1; i <= row; i++) 
			for (int j = 1; j <= col; j++)
				if (arr[i][j] > 0) {
					if (arr[i][j] * cnt > tot) arr[i][j] -= 1;
					else if (arr[i][j] * cnt < tot) arr[i][j] += 1;
				}
	}
}

void rotate(int lev) {
	for (int i = 0; i < k; i++) {
		int temp = arr[lev][col];
		for (int j = col; j > 1; j--)
			arr[lev][j] = arr[lev][j - 1];
		arr[lev][1] = temp;
	}
}

void cal() {
	for (int i = 1; i <= row; i++)
		for (int j = 1; j <= col; j++)
			result += arr[i][j];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col >> query;
	for (int i = 1; i <= row; i++)
		for (int j = 1; j <= col; j++)
			cin >> arr[i][j];
	for (int i = 0; i < query; i++) {
		cin >> num >> dir >> k;
		if (dir == 1) k = col - k;
		for (int j = 1; j <= row; j++) {
			if (j%num == 0) {
				rotate(j);
			}
		}
		bfs();
	}
	cal();
	cout << result;
	return 0;
}