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

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

 

 

시뮬레이션 + bfs(?) 로 풀리는 간단한(?) 문제.

다음과 같은 방법으로 풀 수 있다.

 

1. 원판을 돌린다. 이 때 반시계방향으로 k번 돌리는 것은, 시계 방향으로 M-k번 돌리는 것과 같기 때문에

시계 방향으로 돌리는 것만 구현했다. 효율적인 방식은 아니지만 빠르게 구현하기 위해서(^^;)...

2. 각 지점에서 bfs를 돌면서 인접한 수가 같은지 확인한다. 같은 수는 모두 0으로 바꾸어준다.

2-1. 인접한 수가 모두 다르다면 전체 수의 평균을 구한 다음 조건에 따라 1을 더하거나 빼준다.

3. T회 반복한다

 

전체 코드

전체 코드

#include <iostream>
#include <queue>

using namespace std;
int N, M, T, x, d, k;
int circles[51][50];

int rd[4] = { 0,0,+1,-1 };
int cd[4] = { +1,-1,0,0 };


void rotate(int x, int d, int k) {
	int t = k;
	if (d == 1) {
		t = M - k;
	}

	int multiplier = x;

	for (int k = 0; k < t; k++) {
		for (int i = 1;; i++) {
			multiplier = x * i;
			if (multiplier > N) break;

			int tmp = circles[multiplier][M-1];
			for (int j = M-2; j >= 0; j--) {
				circles[multiplier][j + 1] = circles[multiplier][j];
			}
			circles[multiplier][0] = tmp;
		}
	}
}

bool bfs(int r, int c) {
	queue<pair<int,int>> q;
	vector<pair<int, int>> list;
	bool v[51][51] = { false, };

	q.push(make_pair(r, c));
	list.push_back(make_pair(r, c));
	v[r][c] = true;
	int nr, nc, cr, cc;

	while (!q.empty()) {
		cr = q.front().first;
		cc = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			nr = cr + rd[i];
			nc = cc + cd[i];

			if (nc == -1) nc = M-1;
			else if (nc == M) nc = 0;

			if (nr == 0 || nr == N + 1) continue;
			if (v[nr][nc]) continue;
			if (circles[nr][nc] != circles[r][c]) continue;
				
			v[nr][nc] = true;
			q.push(make_pair(nr, nc));
			list.push_back(make_pair(nr, nc));
		}
	}

	if (list.size() == 1) return false;
	else {
		for (int i = 0; i < list.size(); i++) {
			circles[list[i].first][list[i].second] = 0;
		}
		
		return true;
	}

}

pair<double,double> avg() {
	double sum= 0.0, cnt=0.0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (circles[i][j] == 0) continue;

			sum += circles[i][j];
			cnt++;
		}
	}
	return make_pair(sum, cnt);

}


void run(int x, int d, int k) {
	if(k != 0) rotate(x, d, k);

	bool flag = true;
	double sum = 0;
	double cnt = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {

			if (circles[i][j] == 0) continue;
			if (bfs(i, j)) flag = false;
		}
	}

	if (flag) {
		pair<double, double> p;
		p = avg();
		sum = p.first;
		cnt = p.second;
		if (cnt != 0) {
			double mean = sum / cnt;
			for (int i = 1; i <= N; i++) {
				for (int j = 0; j < M; j++) {
					if (circles[i][j] == 0) continue;

					if (circles[i][j] < mean) circles[i][j] += 1;
					else if (circles[i][j] > mean) circles[i][j] -= 1;
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> T;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> circles[i+1][j];
		}
	}
	for (int i = 0; i < T; i++) {
		cin >> x >> d >> k;
			run(x, d, k);
	}
	
	

	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			ans += circles[i + 1][j];
		}
	}
	cout << ans;
}

 

 

반성(...)

bfs로 다음 탐색을 진행할 때 nc를 바꿔주는 조건을

if (cc == 0 && i == 0) nc = M-1; 
else if (cc == M-1 && i == 1) nc = 0;

라는 이상한 조건을 걸어주는 바람에 뻘짓을 엄청나게 했다^^;

원래 의도는 nc가 -1 이나 M이 되면 M과 0으로 바꾸어 주려는 것이었는데,

두 줄 모두 원래 의도했던 조건에서 작동하지 않는다

(cd의 인덱스를 착각했었다. 그리고 애초에 nc == -1 이나 nc == M으로 짜면 더 간단했는데 왜 이렇게 했을까? 나도 날 모르겠다ㅠㅠ)