컴퓨터 사이언스/1고리즘
백준 17822 : 원판 돌리기
저세상 개발자
2021. 9. 5. 00:04
https://www.acmicpc.net/problem/17822
단순 구현문제다. 크기가 50 x 50 밖에 안되므로 시간 걱정하지말고 시원하게 구현하면 된다.
각각의 원판은 사실 인덱스 범위를 벗어날 시 배열의 반대쪽 끝으로 이어진다는 점을 제외하곤 1차원 배열과 동일하다.
1. 주어진 명령대로 원판을 회전시킨다.
2. 회전 후 삭제 작업을 수행한다.
이 때, bfs를 사용하여 동일한 값을 찾아 지워준다.
#include <iostream>
#include <queue>
using namespace std;
int n, m;
int board[51][51];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
void post_process() {
int curx, cury, nx, ny, cur_val, cnt = 0;
bool is_deleted, cur_deleted;
double sum = 0;
queue<pair<int, int>> q;
is_deleted = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!board[i][j]) continue;
cur_val = board[i][j];
cur_deleted = 0;
sum += cur_val;
++cnt;
q.emplace(j, i);
while (!q.empty()) {
curx = q.front().first, cury = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
nx = curx + dx[i], ny = cury + dy[i];
if (nx <= 0) nx += m;
else if (nx > m) nx -= m;
if (ny <= 0 || ny > n || board[ny][nx] != cur_val) continue;
board[ny][nx] = 0;
q.emplace(nx, ny);
is_deleted = 1;
}
}
if (cur_deleted) {
is_deleted = 1;
board[i][j] = 0;
}
}
}
if (!is_deleted) {
sum /= cnt;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!board[i][j]) continue;
if (board[i][j] > sum) --board[i][j];
else if (board[i][j] < sum) ++board[i][j];
}
}
}
}
void rotate(int x, int d, int k) {
if (d) k = m - k;
int idx;
int tmp[50];
for (int c = x; c <= n; c += x) {
for (int i = 1; i <= m; i++) tmp[i] = board[c][i];
for (int i = 1; i <= m; i++) {
idx = i + k;
if (idx > m) idx -= m;
board[c][idx] = tmp[i];
}
}
post_process();
}
void solution() {
int t, x, d, k, sum = 0;
cin >> n >> m >> t;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> board[i][j];
}
}
while (t--) {
cin >> x >> d >> k;
rotate(x, d, k);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum += board[i][j];
}
}
cout << sum;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solution();
return 0;
}
메모리: 2036 kb | 시간: 4 ms |