<Baekjoon> #17822 Deque, BFS, Simulation_원판 돌리기 c++

⭕ Solution & Idea

• 원판을 한 칸씩 돌릴 때마다 원판의 마지막 값이 가장 앞으로 오고, 앞의 값이 마지막 값으로 간다는 점에서 deque 자료 구조를 이용한다
• 이웃한 원판의 수를 지울 때 bfs, 너비 우선 탐색을 이용하는데 이때 같은 원판 내에서 처음 끝과 마지막 값이 이웃한다는 점을 주의한다

⭕ 1. roate

• 시계 방향으로 회전했을 경우 원판의 변화를 보면 가장 마지막 값이 앞으로 가는 것을 알 수 있다
  
• 시계 반대 방향으로 회전했을 경우는 가장 첫 번째 값이 마지막으로 간다
• x는 회전할 원판의 배수, i는 회전할 원판의 번호, j는 회전 수

void rotate(int x, int d, int k) {
	int p = x;
	int idx = 1;
	for (int i=p; i<=N; i=p*idx) {
		for (int j = 0; j < k; j++) {

			if (d == 0) {
				int back = dq[i].back();
				dq[i].pop_back();
				dq[i].push_front(back);
			}
			else if (d == 1) {
				int front = dq[i].front();
				dq[i].pop_front();
				dq[i].push_back(front);
			}
		}
	idx++;
	}
}

⭕ 2. find adjacent

• visited[][]를 두어 0이 아닌 원판의 모든 위치를 방문하여 인접한 값중에 같은 값이 있는지 조사한다

for (int i = 1; i <= N; i++) {
	for (int j = 0; j < M; j++) {
		if (!visited[i][j] && dq[i][j]!=0)
			bfs(i, j);
	}
}

• bfs 함수 내에서 주의할 점은 한 원판 내에서 첫 번째 값과 마지막 값은 이웃한다는 것이다
  e.g. 다음과 같은 경우
  3번 째 원판 dq[3]={4, x, x, 4}가 저장되어 있어 일반적인 너비 우선 탐색을 사용하면 첫 번째 값과 마지막 값이 이웃하지 않은 것 처럼 나온다
  
  따라서 아래와 같이 4번째 원판의 이웃은 0번, 0번째 이웃은 4번으로 만들어준다

	if (nx < 0 ) 
	nx = M - 1;
	if (nx >= M)
	nx = 0;

⭕ 3. change Value

• 만약 제거되는 값이 하나도 없다면 평균 값을 구해 값을 변경해주어야 한다. 이때 주의할 점은 평균 값을 double로 만들어주어야 한다는 것!!

	if (!changed) {
		double sum = 0, avg = 0,n=0;
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < M; j++) {
				if (dq[i][j] != 0) {
					sum += dq[i][j];
					n++;
				}
			}
		}

		avg = sum / n;

		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < M; j++) {
				if (dq[i][j] != 0) {
					if ((double)dq[i][j] < avg) dq[i][j]++;
					else if ((double)dq[i][j] > avg) dq[i][j]--;
				}
			}
		}
	}

⭕ Source Code

#include <iostream>
#include <deque>
#include <string.h>
#include <queue>

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

using namespace std;

int ret;
int N, M, T;
deque<int> dq[MAX];
bool visited[MAX][MAX];
bool changed;

void print() {
	printf("\n");
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			printf("%d ", dq[i][j]);
		}
		printf("\n");
	}
}

void bfs(int i, int j) {
	int num = dq[i][j];
	visited[i][j] = true;

	queue<pair<int, int>> q;
	q.push(make_pair(i, j));

	bool flag = false;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny <= 0 || ny>N) continue;
	
			if (nx < 0 ) 
				nx = M - 1;
			if (nx >= M)
				nx = 0;

			if (dq[ny][nx] == 0) continue;
			if (!visited[ny][nx] && dq[ny][nx] == num) {
				flag = true;
				visited[ny][nx] = true;
				dq[ny][nx] = 0;
				q.push(make_pair(ny, nx));
			}
		}
	}
	if (flag) {
		dq[i][j] = 0;
		changed = true;
	}
}

void find_adj () {
	memset(visited, false, sizeof(visited));

	changed = false;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (!visited[i][j] && dq[i][j]!=0)
				bfs(i, j);
		}
	}

	//print();

	if (!changed) {
		double sum = 0, avg = 0,n=0;
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < M; j++) {
				if (dq[i][j] != 0) {
					sum += dq[i][j];
					n++;
				}
			}
		}

		avg = sum / n;

		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < M; j++) {
				if (dq[i][j] != 0) {
					if ((double)dq[i][j] < avg) dq[i][j]++;
					else if ((double)dq[i][j] > avg) dq[i][j]--;
				}
			}
		}
	}

	//print();
}

void rotate(int x, int d, int k) {
	int p = x;
	int idx = 1;
	for (int i=p; i<=N; i=p*idx) {
		for (int j = 0; j < k; j++) {

			if (d == 0) {
				int back = dq[i].back();
				dq[i].pop_back();
				dq[i].push_front(back);
			}
			else if (d == 1) {
				int front = dq[i].front();
				dq[i].pop_front();
				dq[i].push_back(front);
			}
		}
	idx++;
	}
}

void solution() {
	while (T--) {
		int x, d, k;
		cin >> x >> d >> k;
		rotate(x,d,k);

		//print();

		find_adj();
	}
	for (int i = 1; i <= N; i++)
		for (int j = 0; j < M; j++)
			ret += dq[i][j];

}

void input() {
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			int n; cin >> n;
			dq[i].push_back(n);
		}
	}
}

int main() {
	input();
	solution();

	printf("%d\n", ret);
}

23일 전엔 못 풀고 지나갔던 문젠데 오늘 풀었을 땐 쉽게 풀렸다..