[Algorithm] 백준 17822 원판 돌리기c++

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

17822번: 원판 돌리기

풀이

시뮬레이션

• 주어진 조건 그대로 구현하면 된다.
• xi의 배수의 원판 구하기
  • 배수를 구하는 법: xi만큼 계속 더한다 (j += xi)
• 원판 회전시키기
  • 시계 방향: tmp에 이동 후 인덱스를 넣는다.  
  • 반시계 방향: tmp에 이동 전 인덱스를 넣는다.
• 인접한 수 확인하기
  • same은 인접하면서 수가 같은 것이 있으면 true, 없으면 false를 나타낸다.
  • tmp배열은 시뮬레이션에 동시 처리를 위한 임시 변수이다. 동시에 일어나는 일을 코드 상에서 구현할 때는 이렇게 임시 변수를 도입해 별로도 처리하고, 나중에 본 변수를 덮어쓰는 방식으로 구현한다.
• 인접하면서 수가 같은 것이 없는 경우
  • 평균을 구할 때, double을 사용하는 것 보다 나누기를 곱하기로 바꿔서 계산하는 것이 간단하고 명확하다. 

소스코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int a[51][51];

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

int main(){
	int n, m, t;
	cin>>n>>m>>t;

	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cin>>a[i][j];

	for(int i=0; i<t; i++){
		int xi, di, ki;
		cin>>xi>>di>>ki;

		//x의 배수 원판 회전
		for(int j=xi; j<=n; j+=xi){
			int b[m];
			memset(b, 0, sizeof(b));
			if(di == 0){ //시계
				for(int idx=0; idx<m; idx++){
					int tmp = (idx+ki)%m;
					b[tmp] = a[j-1][idx];
				}
			} else{ //반시계
				for(int idx=0; idx<m; idx++){
					int tmp = (idx+ki)%m;
					b[idx] = a[j-1][tmp];
				}
			}
			for(int idx=0; idx<m; idx++){
				a[j-1][idx] = b[idx];
			}
		}

		//인접한 수 체크
		bool same = false; //인접한 수가 같은 것이 있는 경우 true
		bool tmp[n][m]; //동시 처리를 위한 임시 변수
		memset(tmp, 0, sizeof(tmp));
		for(int x=0; x<n; x++){
			for(int y=0; y<m; y++){
				bool flag = false;
				if(a[x][y] == 0) continue;
				for(int k=0; k<4; k++){
					int nx = x + dx[k];
					int ny = y + dy[k];

					if(nx < 0 || nx >=n ) continue;

					if(ny == -1) ny = m-1;
					if(ny == m) ny = 0;

					if(a[x][y] == a[nx][ny]){
						flag = true;
						same = true;
						tmp[nx][ny] = 1;
					}
				}
				if(flag){
					tmp[x][y] = 1;
				}
			}
		}

		//인접하면서 같은 수 지우기
		for(int j=0; j<n; j++){
			for(int k=0; k<m; k++){
				if(tmp[j][k]) a[j][k] = 0;
			}
		}

		if(!same){
			int sum = 0;
			int cnt = 0;
			for(int j=0; j<n; j++){
				for(int k=0; k<m; k++){
					if(a[j][k] != 0){
						sum += a[j][k];
						cnt++;
					}
				}
			}
			for(int j=0; j<n; j++){
				for(int k=0; k<m; k++){
					if(a[j][k] != 0){
						if(a[j][k] * cnt > sum) a[j][k] -= 1;
						else if(a[j][k] * cnt < sum) a[j][k] += 1;
					}
				}
			}
		}
	}

	int ans = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++)
			ans += a[i][j];
	}
	cout<<ans<<'\n';

	return 0;
}