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

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

17822번: 원판 돌리기

 

개인적으로 많이 예외를 못찾아서 고민한 문제....

 

이런 문제일수록 구현을 간단하게 설계해야 한다.

 

구현해야할 것은 크게 

 

• 0. 입력
• 1. 원판 돌리기
• 2. 인접한 수 탐색
• 2-1. 인접한 수 지우기
• 2-2.  평균값에서 감산, 가감하기
• 3. 결과 도출

깨알팁 tip)

 

1. 원판 돌리기 같은경우에 시계 반대 방향은 m - k 번 시계방향으로 돌리는 것과 같다.

2. 인접한 수를 탐색하는 bfs 구현시 배열을 통해서 구현 범위를 줄일 수 있다.

 

 

 

아래는 정답 코드입니다.

 

#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

int n, m, t;
int arr[51][51] = { 0, };
int result = 0;
int temp[51] = { 0, };
int visited[51][51];

int y_ar[4] = { 1,-1,0,0 };
int x_ar[4] = { 0,0,1,-1 };

//2. search
bool bfs(int y, int x) {

	memset(visited, 0, sizeof(visited));

	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1;

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

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny < 0 || ny == n) continue;

			if (nx == m) nx = 0;
			else if (nx == -1) nx = m - 1;

			if (visited[ny][nx] == 0 && arr[ny][nx] == arr[cy][cx]) {
				que.push(make_pair(ny, nx));
				visited[ny][nx] = visited[cy][cx] + 1;
			}

		}
	}

	//erase
	bool jud = false;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (visited[i][j] > 1)
				jud = true;
	if (jud == true) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (visited[i][j] != 0)
					arr[i][j] = 0;
	}
	return jud;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	//0. init
	cin >> n >> m >> t;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];

	while (t--) {
		int x, d, k;
		cin >> x >> d >> k;
		if (d == 1)
			k = m - k;
		//1. 회전
		for (int i = x - 1; i < n; i += x) {
			
			for (int l = 0; l < k; l++) {
				for (int j = 0; j < m; j++)
					temp[j] = arr[i][j];

				for (int j = 1; j < m; j++)
					arr[i][j] = temp[j - 1];
				arr[i][0] = temp[m - 1];
			}
		}



		
		bool jud = false;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				if (visited[i][j] == 0 && arr[i][j] != 0) {
					
					bool temp = bfs(i, j);
					if (temp == true)
						jud = true;
				}
			}

		//평균값 구해서 +1, -1  해주기
		if (jud == false) { 
			double sum = 0;
			double cnt = 0;
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					if (arr[i][j] != 0 ) {
						sum += arr[i][j];
						cnt += 1;
					}
			if (cnt > 0) {
				sum = sum / cnt;
				for (int i = 0; i < n; i++)
					for (int j = 0; j < m; j++)
						if (arr[i][j] != 0) {
							if (sum > arr[i][j])
								arr[i][j] ++;
							else if (sum < arr[i][j])
								arr[i][j] --;
						}
			}
		}


	}


	//result
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			result += arr[i][j];
	cout << result << endl;

	
}