<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일 전엔 못 풀고 지나갔던 문젠데 오늘 풀었을 땐 쉽게 풀렸다..
Author And Source
이 문제에 관하여(<Baekjoon> #17822 Deque, BFS, Simulation_원판 돌리기 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon-17822-Deque-BFS-Simulation원판-돌리기-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)