백준 17822 원판 돌리기 C++

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

17822번: 원판 돌리기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ17822.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ17822
//
//  Created by 최화연 on 2022/04/25.
//

#include <iostream>
#include <deque>
#include <cstring>
#include <queue>
using namespace std;

int N, M, T;

//circle[i][j] = i번째 원판에 적힌 j번째 수
deque<deque<int>> circles = {{}, };
int visits[51][51] = {0, };

void rotate_circle(int x, int d, int k) {
    for (int i=x; i<=N; i+=x) {
        //시계
        if (d == 0) {
            for (int j=0; j<k; j++) {
                int num = circles[i].back();
                circles[i].pop_back();
                circles[i].push_front(num);
            }
        }
        //반시계
        else {
            for (int j=0; j<k; j++) {
                int num = circles[i].front();
                circles[i].pop_front();
                circles[i].push_back(num);
            }
        }
    }
}

int erase_num(int si, int sj, int num) {
    int cnt = 1;
    visits[si][sj] = 1;
    queue<pair<int, int>> q;
    q.push({si, sj});
    
    while (!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        if (j == M-1) {
            if (circles[i][0] == num && visits[i][0] == 0) {
                visits[i][0] = 1;
                circles[i][0] = 0;
                cnt ++;
                q.push({i, 0});
            }
            if (circles[i][M-2] == num && visits[i][M-2] == 0) {
                visits[i][M-2] = 1;
                circles[i][M-2] = 0;
                cnt ++;
                q.push({i, M-2});
            }
        }
        else if (j == 0) {
            if (circles[i][1] == num && visits[i][1] == 0) {
                visits[i][1] = 1;
                circles[i][1] = 0;
                cnt ++;
                q.push({i, 1});
            }
            if (circles[i][M-1] == num && visits[i][M-1] == 0) {
                visits[i][M-1] = 1;
                circles[i][M-1] = 0;
                cnt ++;
                q.push({i, M-1});
            }
        }
        else {
            if (circles[i][j-1] == num && visits[i][j-1] == 0) {
                visits[i][j-1] = 1;
                circles[i][j-1] = 0;
                cnt ++;
                q.push({i, j-1});
            }
            if (circles[i][j+1] == num && visits[i][j+1] == 0) {
                visits[i][j+1] = 1;
                circles[i][j+1] = 0;
                cnt ++;
                q.push({i, j+1});
            }
        }
        
        if (i < N) {
            if (circles[i+1][j] == num && visits[i+1][j] == 0) {
                visits[i+1][j] = 1;
                circles[i+1][j] = 0;
                cnt ++;
                q.push({i+1, j});
            }
        }
        
        if (i > 1) {
            if (circles[i-1][j] == num && visits[i-1][j] == 0) {
                visits[i-1][j] = 1;
                circles[i-1][j] = 0;
                cnt ++;
                q.push({i-1, j});
            }
        }
    }
    
    if (cnt > 1) circles[si][sj] = 0;
    return cnt;
}

int main(int argc, const char * argv[]) {
    cin >> N >> M >> T;
    for (int i=1; i<=N; i++) {
        deque<int> circle;
        for (int j=1; j<=M; j++) {
            int n;
            cin >> n;
            circle.push_back(n);
        }
        circles.push_back(circle);
    }
    
    int x, d, k;
    for (int t=0; t<T; t++) {
        cin >> x >> d >> k;
        rotate_circle(x, d, k);
        
        memset(visits, 0, sizeof(visits));
        int erase_cnt = 0;
        int non_cnt = 0;
        int sum = 0;
        for (int i=1; i<=N; i++) {
            for (int j=0; j<M; j++) {
                if (visits[i][j] || circles[i][j] == 0) continue;
                int num = circles[i][j];
                int same = erase_num(i, j, num);
                if (same == 1) {
                    sum += num;
                    non_cnt ++;
                }
                else {
                    sum += same*num;
                    erase_cnt += same;
                }
            }
        }
        
        if(sum == 0) {
            cout << 0 << endl;
            return 0;
        }
        
        if(erase_cnt == 0) {
            double average = (double)sum/double(non_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] > average) circles[i][j] --;
                    else if (circles[i][j] < average) circles[i][j] ++;
                }
            }
        }
    }
    
    int answer = 0;
    for (int i=1; i<=N; i++) {
        for (int j=0; j<M; j++) {
            answer += circles[i][j];
        }
    }
    cout << answer << endl;
    
    return 0;
}

---

풀이 과정

풀이 시간 1시간 33분

#include <iostream>
#include <deque>
#include <cstring>
#include <queue>
using namespace std;

int N, M, T;

//circle[i][j] = i번째 원판에 적힌 j번째 수
deque<deque<int>> circles = {{}, };
int visits[51][51] = {0, };

void rotate_circle(int x, int d, int k) {
    for (int i=x; i<=N; i+=x) {
        //시계
        if (d == 0) {
            for (int j=0; j<k; j++) {
                int num = circles[i].back();
                circles[i].pop_back();
                circles[i].push_front(num);
            }
        }
        //반시계
        else {
            for (int j=0; j<k; j++) {
                int num = circles[i].front();
                circles[i].pop_front();
                circles[i].push_back(num);
            }
        }
    }
}

int erase_num(int si, int sj, int num) {
    int cnt = 1;
    visits[si][sj] = 1;
    queue<pair<int, int>> q;
    q.push({si, sj});
    
    while (!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        if (j == M-1) {
            if (circles[i][0] == num && visits[i][0] == 0) {
                visits[i][0] = 1;
                circles[i][0] = 0;
                cnt ++;
                q.push({i, 0});
            }
            if (circles[i][M-2] == num && visits[i][M-2] == 0) {
                visits[i][M-2] = 1;
                circles[i][M-2] = 0;
                cnt ++;
                q.push({i, M-2});
            }
        }
        else if (j == 0) {
            if (circles[i][1] == num && visits[i][1] == 0) {
                visits[i][1] = 1;
                circles[i][1] = 0;
                cnt ++;
                q.push({i, 1});
            }
            if (circles[i][M-1] == num && visits[i][M-1] == 0) {
                visits[i][M-1] = 1;
                circles[i][M-1] = 0;
                cnt ++;
                q.push({i, M-1});
            }
        }
        else {
            if (circles[i][j-1] == num && visits[i][j-1] == 0) {
                visits[i][j-1] = 1;
                circles[i][j-1] = 0;
                cnt ++;
                q.push({i, j-1});
            }
            if (circles[i][j+1] == num && visits[i][j+1] == 0) {
                visits[i][j+1] = 1;
                circles[i][j+1] = 0;
                cnt ++;
                q.push({i, j+1});
            }
        }
        
        if (i < N) {
            if (circles[i+1][j] == num && visits[i+1][j] == 0) {
                visits[i+1][j] = 1;
                circles[i+1][j] = 0;
                cnt ++;
                q.push({i+1, j});
            }
        }
        
        if (i > 1) {
            if (circles[i-1][j] == num && visits[i-1][j] == 0) {
                visits[i-1][j] = 1;
                circles[i-1][j] = 0;
                cnt ++;
                q.push({i-1, j});
            }
        }
    }
    
    if (cnt > 1) circles[si][sj] = 0;
    return cnt;
}

int main(int argc, const char * argv[]) {
    cin >> N >> M >> T;
    for (int i=1; i<=N; i++) {
        deque<int> circle;
        for (int j=1; j<=M; j++) {
            int n;
            cin >> n;
            circle.push_back(n);
        }
        circles.push_back(circle);
    }
    
    int x, d, k;
    for (int t=0; t<T; t++) {
        cin >> x >> d >> k;
        rotate_circle(x, d, k);
        
        memset(visits, 0, sizeof(visits));
        int erase_cnt = 0;
        int non_cnt = 0;
        int sum = 0;
        for (int i=1; i<=N; i++) {
            for (int j=0; j<M; j++) {
                if (visits[i][j] || circles[i][j] == 0) continue;
                int num = circles[i][j];
                int same = erase_num(i, j, num);
                if (same == 1) {
                    sum += num;
                    non_cnt ++;
                }
                else {
                    sum += same*num;
                    erase_cnt += same;
                }
            }
        }
        
        if(sum == 0) {
            cout << 0 << endl;
            return 0;
        }
        
        if(erase_cnt == 0) {
            double average = (double)sum/double(non_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] > average) circles[i][j] --;
                    else if (circles[i][j] < average) circles[i][j] ++;
                }
            }
        }
    }
    
    int answer = 0;
    for (int i=1; i<=N; i++) {
        for (int j=0; j<M; j++) {
            answer += circles[i][j];
        }
    }
    cout << answer << endl;
    
    return 0;
}

---

이전 풀이

풀이 시간 1시간 9분

#include <iostream>
#include <deque>
using namespace std;

int N, M, T;

//board[i][j] = i번째 원판에 적힌 j번째 값
int board[50][50] = {0, };

struct Command{
    int x;
    int d;
    int k;
};
deque<Command> cmds;
Command cmd;
int answer = 0;

void rotate(){
	//원판을 회전할 때 사용할 덱
    deque<int> x_board;
    //인접한 같은 수를 가진 위치들을 저장할 덱
    deque<pair<int, int>> erase;
    
    while(!cmds.empty()){
        cmd = cmds.front();
        cmds.pop_front();
        
        //1. x 배수의 원판을 회전시킨다
        for(int x=cmd.x-1; x<N; x+=cmd.x){
            x_board.clear();
            //현재 원판의 값을 x_board에 담아준다
            for(int j=0; j<M; j++){
                x_board.push_back(board[x][j]);
            }
            //시계방향 회전
            if(cmd.d == 0){
            	//k번 뒤에 있는 값을 맨 앞으로 옮긴다
                for(int k=0; k<cmd.k; k++){
                    int temp = x_board.back();
                    x_board.pop_back();
                    x_board.push_front(temp);
                }
            }
            //반시계방향 회전
            else{
            	//k번 앞에 있는 값을 맨 뒤로 옮긴다
                for(int k=0; k<cmd.k; k++){
                    int temp = x_board.front();
                    x_board.pop_front();
                    x_board.push_back(temp);
                }
            }
            //회전한 값을 원판에 넣어준다
            for(int j=0; j<M; j++){
                board[x][j] = x_board[j];
            }
        }
        
        //2. 인접한 값을 탐색한다
        erase.clear();
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(board[i][j] == 0) continue;
                if(j < M-1){
                	//현재 칸의 값이 다음 칸의 값과 같은 경우, erase에 위치 값을 담는다
                    if(board[i][j] == board[i][j+1]){
                        erase.push_back({j, i});
                        erase.push_back({j+1, i});
                        
                        //인접한 원판 값과 같은 경우, erase에 위치 값을 담는다
                        if(i < N-1){
                            if(board[i][j] == board[i+1][j]){
                                erase.push_back({j, i+1});
                            }
                        }
                    }
                    else if(i < N-1){
                    	//인접한 원판 값과 같은 경우, erase에 위치 값을 담는다
                        if(board[i][j] == board[i+1][j]){
                            erase.push_back({j, i});
                            erase.push_back({j, i+1});
                        }
                    }
                }
                else {
                    if(i < N-1){
                    	//인접한 원판 값과 같은 경우, erase에 위치 값을 담는다
                        if(board[i][j] == board[i+1][j]){
                            erase.push_back({j, i});
                            erase.push_back({j, i+1});
                        }
                    }
                    //현재 칸의 값이 다음 칸의 값과 같은 경우, erase에 위치 값을 담는다
                    if(board[i][j] == board[i][0]){
                        erase.push_back({j, i});
                        erase.push_back({0, i});
                    }
                }
            }
        }
        
        //2-1. 인접하면서 같은 수를 가진 것이 있는 경우, 지운다
        if(erase.size() > 0){
            for(int i=0; i<erase.size(); i++){
                board[erase[i].second][erase[i].first] = 0;
            }
        }
        //2-2. 지울 것이 없는 경우
        else{
        	//원판의 모든 값의 합을 구한다
            int cnt = 0;
            int sum = 0;
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(board[i][j] == 0) continue;
                    sum += board[i][j];
                    cnt++;
                }
            }
            //모든 원판의 값이 0인 경우, while문을 빠져나온다
            if(sum == 0){
                answer = 0;
                break;
            }
            
            double avg = (double)sum/cnt;
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(board[i][j] == 0) continue;
                    //원판의 평균값보다 작은 경우, 값을 1 더한다
                    if(board[i][j] < avg) board[i][j]++;
                    //원판의 평균값보다 큰 경우, 값을 1 뺀다
                    else if(board[i][j] > avg) board[i][j] --;
                }
            }
        }
        
        //3. 원판의 모든 값의 합을 answer에 갱신한다
        answer = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(board[i][j] == 0) continue;
                answer += board[i][j];
            }
        }
        //원판의 모든 값이 0인 경우, while문을 빠져나간다
        if(answer == 0) break;
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M >> T;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> board[i][j];
        }
    }
    for(int t=0; t<T; t++){
        cin >> cmd.x >> cmd.d >> cmd.k;
        cmds.push_back(cmd);
    }
    rotate();
    cout << answer << endl;
    
    return 0;
}
//시간복잡도 = T(T*N*M^2) -> O(N^4), 공간복잡도 = O(N^2)