⭕ Solution & Idea
deque
자료 구조를 이용한다⭕ 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
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
함수 내에서 주의할 점은 한 원판 내에서 첫 번째 값과 마지막 값은 이웃한다는 것이다dq[3]={4, x, x, 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일 전엔 못 풀고 지나갔던 문젠데 오늘 풀었을 땐 쉽게 풀렸다..