[BOJ] 17822번 원판 돌리기

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

17822번: 원판 돌리기

작년 하반기 삼성 기출문제

주사위 윷놀이와 같이 나온 문제로 알고 있는데,

이것도 2달 전에 풀었는데 반례를 찾지 못해서 방치했다가 이제서야 풀었다.

그 때는 회전하는 방식을 쓸데 없이 어렵게 했었는데

그냥 복사하는게 쉽고 맘 편하다..

 

 

문제

원판 T번 회전시킨 후 원판에 적힌 수의 합 구하기

 

 

풀이

BFS + 시뮬레이션

원판을 배열로 표현할 줄 알아야 겠다(물론 문제보면 알 수 있지만)

BFS할때 원형이므로 [i][M]과 [i][1]이 인접해 있음만 주의하면 어렵진 않은듯 하다.

1. 먼저, 회전한다.
2. 그리고 visited 배열 초기화 하고, 인접한 같은 수들 찾아서 지워준다.
3. 만약 인접한 같은 수가 없다면 현재 지워지지 않은 수들의 평균을 구하고, 평균보다 큰 수는 1 감소하고, 평균보다 작은 수는 1 증가한다.
4. T번의 회전이 끝나면 원판에 있는 수의 합을 구한다.

 

 

실수 했던 부분

• 숫자를 지워줄 때, 현재노드와 다음노드를 같이 지웠는데, 이렇게 되면 맨 처음에 BFS를 시작하는 숫자를 처음부터 지우게 되어 BFS가 2번뿐이 진행되지 않는 상황이 발생했다.
• 회전하는 것을 그냥 복사하면 되는데 어렵게 생각했다. A형 문제는 효율성 생각하지 말자

 

항상 초기화 하는거 잊지 말고 차근 차근 코딩하기

 

 

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

#include <iostream>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;

int N, M, T, x, d, k, answer;
int map[51][51];
bool visited[51][51];
int temp[51];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

int main() {
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
		}
	}

	while (T--) {
		cin >> x >> d >> k;
		
		//회전하는 과정
		if (d == 1) k = (M - k);

		for (int i = x; i <= N; i += x) {
			for (int j = 1; j <= M; j++) {
				int nj = (j + k) % M;
				if (nj == 0) nj = M;
				temp[nj] = map[i][j];
			}

			for (int j = 1; j <= M; j++) {
				map[i][j] = temp[j];
			}
		}

		//먼저 visited 초기화
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				visited[i][j] = false;
			}
		}

		bool flag = false;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (map[i][j] == 0) continue;
				if (visited[i][j]) continue;
				int num = map[i][j];

				queue<pair<int, int>> q;
				q.push({ i,j });
				visited[i][j] = true;

				while (!q.empty()) {
					int cy = q.front().first;
					int cx = q.front().second;
					q.pop();

					for (int k = 0; k < 4; k++) {
						int ny = cy + dy[k];
						int nx = cx + dx[k];

						if (nx == 0) nx = M;
						if (nx == M + 1) nx = 1;

						if (ny < 1 || ny > N) continue;
						if (map[ny][nx] != num) continue;
						if (visited[ny][nx]) continue;

						flag = true;

						q.push({ ny,nx });
						visited[ny][nx] = true;
						map[cy][cx] = 0;
						map[ny][nx] = 0;
					}
				}
				
			}
		}

		if (!flag) {
			double aver = 0;
			int cnt = 0;
			
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					if (map[i][j] > 0) {
						aver += map[i][j];
						cnt++;
					}
				}
			}
		
			aver /= cnt;
		
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					if(map[i][j] == 0) continue;
					
					if (map[i][j] > aver) {
						map[i][j]--;
					}
					else if (map[i][j] < aver) {
						map[i][j]++;
					}
				}
			}
		}

	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			answer += map[i][j];
		}
	}

	cout << answer;
}