[삼성] 17822 원판돌리기

원판을 돌린다는 이유로 deque 자료구조를 이용했다. 그리고 이웃하는 수를 제거하는 과정은 bfs를 통해 각 노드들은 한 번만 접근하도록 했다. double 계산을 위해 합을 double로 선언했는데, 마지막에는 int로 선언해야 한다는 점을 망각해서 오류를 범했다

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/17822.cpp

 

	#include <tuple>
	#include <queue>
	#include <deque>
	#include <vector>
	#include <iostream>
	using namespace std;
	int dx[4] = { 1, -1, 0, 0 };
	int dy[4] = { 0, 0, 1, -1 };
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, t;
	cin >> n >> m >> t;
	vector<deque<int>> vq;
	double tsum = 0;
	int tnum = 0;
	for (int i = 0; i < n; i++) {
	deque<int> dq;
	for (int j = 0; j < m; j++) {
	int x;
	cin >> x;
	tsum += x;
	tnum += 1;
	dq.push_back(x);
	}
	vq.push_back(dq);
	}
	while (t--) {
	int x, d, k;
	cin >> x >> d >> k;
	int st = x - 1;
	for (int i = st; i < n; i += x) {
	if (d == 0) {
	for (int j = 0; j < k; j++) {
	int b = vq[i].back();
	vq[i].pop_back();
	vq[i].push_front(b);
	}
	}
	else {
	for (int j = 0; j < k; j++) {
	int b = vq[i].front();
	vq[i].pop_front();
	vq[i].push_back(b);
	}
	}
	}
	vector<vector<int>> visit(n, vector<int>(m, false));
	bool tok = false;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	if (visit[i][j] || vq[i][j] == 1e8) continue;
	bool ok = false;
	int base = vq[i][j];
	queue<pair<int, int>> q;
	q.push(make_pair(i, j));
	visit[i][j] = true;
	while (!q.empty()) {
	int ti, tj;
	tie(ti, tj) = q.front();
	q.pop();
	for (int dir = 0; dir < 4; dir++) {
	int u = ti + dx[dir];
	int v = tj + dy[dir];
	if (u == -1 || u == n) continue;
	if (v == m) v = 0;
	else if (v == -1) v = m - 1;
	if (vq[u][v] == 1e8 || visit[u][v]) continue;
	if (vq[u][v] == base) {
	vq[u][v] = 1e8;
	q.push(make_pair(u, v));
	visit[u][v] = true;
	tsum -= base;
	tnum -= 1;
	ok = true;
	tok = true;
	}
	}
	}
	if (ok) {
	vq[i][j] = 1e8;
	tsum -= base;
	tnum -= 1;
	}
	}
	}
	if(!tok && tnum > 0) {
	double avg = tsum / tnum;
	for (int ti = 0; ti < n; ti++) {
	for (int tj = 0; tj < m; tj++) {
	if (vq[ti][tj] == 1e8) continue;
	if (avg > vq[ti][tj]) {
	vq[ti][tj] += 1;
	tsum += 1;
	}
	else if (avg < vq[ti][tj]) {
	vq[ti][tj] -= 1;
	tsum -= 1;
	}
	}
	}
	}
	}
	cout << (int)tsum << '\n';
	return 0;
	}

view raw 17822.cpp hosted with ❤ by GitHub