[백준 17822][C++] 원판 돌리기

문제

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

17822번: 원판 돌리기

 

풀이 과정

1. 원판 회전 함수 구현 (회전에 사용할 자료형 선택, 필자는 vector를 이용했다)

2. 회전 후 원판들을 업데이트하는 함수 구현

    2-1. 원판을 탐색하며 인접하면서 같은 수를 모두 지우도록 구현

    2-2. 아무것도 지워지지 않았다면, 평균을 구하여 값을 평균을 기준으로 조정하도록 구현

3. 입력받은 T 개수만큼의 경우에 1번의 함수와 2번의 함수 적용.

 

 

세부 풀이

(1) rotate 함수

필자는 원형으로 순환하는 상황을 표현하기 위해 모든 원판에 대한 정보를 저장하는 자료구조로 벡터를 이용했다.

순환하면 queue 가 생각나서 처음에 queue를 적용하려 했으나, 2번 함수 구현에서 있을 탐색에서 queue는 단점을 갖는다. 따라서 순환하는 시간에서 queue 보다 손해를 보더라도 각 인자에 대한 접근이 쉽고 수정할 수 있는 vector를 이용하여 순환 함수를 구현했다.\

 

Line 115-117에 주요 아이디어가 존재한다. 새로운 벡터를 하나 생성하여, 기존의 벡터의 값들을 원하는 순서대로 넣어준 뒤 업데이트하는 방식으로 구현했다. 이때 순환하는 형태의 특징을 이용하여 하나의 코드로 두 방향에 대한 업데이트를 진행했다.

M개가 순환하는 구조라고 했을 때, 시계방향 k칸 이동은 반시계 방향 (M-K) 칸 이동과 동일하다. 해당 성질을 이용해 코드를 간소화했다.

 

(2-1) update 함수 - 같은 수 지우기

해당 함수는 BFS 형식을 적용하여 구현했다. 이때 map의 index에 주의해야 한다. 주의해야 한다. map은 벡터를 이용한 이중 배열 형태이다. 이때 map의 인덱스에 주의해야 한다. (Row : x로 구현, Col : y로 구현)

 

Row는 원판을 의미하는데, 원판의 시작을 1부터 하기 위해 Row 0 에는 빈 벡터를 넣었다. Col은 각 원소를 의미한다. Col값이 순환 형태에서의 중요한 값이 된다. BFS를 통해 새로운 좌표를 탐색할 때 Col 값이 -1 인 경우 M-1 값이 되도록, Col 값이 M인 경우 0 이 되도록 설정했다.

 

BFS를 진행할 때, 무한 loop에 갇히는 것을 방지하기 위해  map [x][y]의 값을 0으로 설정했다. 이때 map [x][y]를 0으로 변환하기 전에 temp값에 기존의 값을 저장해두었다가 하나의 BFS 내부에서 변경이 한 번도 일어나지 않았다면 다시 원래의 수로 map [x][y]를 복원하도록 구현했다.

 

(2-2) update 함수 - 지우지 않았다면 값 조정

함수 내부에서 2-1 부분을 수행할 때 전역 변수로 선언한 del_flag를 통해 값의 삭제가 이루어졌는지 기록한다. del_flag의 업데이트는 BFS함수 내부에서 값이 변경될 때 del_flag를 true로 수정하게 구현되어 있다.

 

소스코드에도 설명되어 있듯이 위에서 어차피 BFS를 위해 이중 for문을 이용하여 탐색을 진행하는데, Line 147의 조건문에 필요한 값을 같이 업데이트하도록 구현했다.

 

(3) solve 함수

solve 내부에서 T번만큼 rotate와 update를 수행하도록 구현했다. 만약 남은 숫자의 개수가 0이 된다면 break 한다.

이후 map의 값의 합을 구하여 출력한다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>


using namespace std;

int N,M,T, remain_nums;
vector<vector<int>> map;

struct xdk{
    int x,d,k;
};

vector<xdk> v;


void print_map(){
    for(int i=1;i<=N;i++){
        for(int j=0;j<M;j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

void Input(){
    vector<int> temp_v;
    cin >> N >> M >> T;
    int temp;

    //시작 인덱스를 1로 맞추기위해 0번에 0값으로 채우기
    for(int i=0;i<M;i++) temp_v.push_back(0);
    map.push_back(temp_v);

    for(int i=0;i<N;i++){
        temp_v.clear();
        for(int j=0;j<M;j++){
            cin >> temp;
            temp_v.push_back(temp);
        }
        map.push_back(temp_v);
    }
    remain_nums = N*M;
    int x,d,k;
    for(int i=0;i<T;i++){
        cin >> x >> d >> k;
        v.push_back({x,d,k});
    }
}


bool del_flag=false;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
void BFS(int ix, int iy){
    bool BFS_flag=false;
    if(map[ix][iy]==0) return;
    
    queue<pair<int,int>> q;
    int x = ix, y = iy;
    int temp = map[x][y];
    //초기 BFS 탐색 시 우선 삭제한다. flag 통해 변화 없으면 복구한다.
    map[x][y]=0;
    remain_nums--;

    q.push({x,y});
    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int newX = x+dir[i][0];
            int newY = y+dir[i][1];
            // //이미 삭제되어 없는 경우
            // if(map[newX][newY]==0) continue;
            //범위를 벗어나는 경우 (y좌표는 원형 순환이므로 한칸 씩 여유있게 확보)
            if(newX<1 || newX>N || newY<-1 || newY>M) continue;
            //원형 순환에 맞게 index 조정
            if(newY==-1) newY = M-1;
            else if(newY==M) newY = 0;

            if(temp==map[newX][newY]){
                BFS_flag = true;
                del_flag = true;
                map[newX][newY] = 0;
                remain_nums--;
                q.push({newX,newY});
            }
        }
    }
    //지워진 것이 없다면 복구
    if(!BFS_flag){
        map[x][y]=temp;
        remain_nums++;
    }
    return;
}

/* 
 * x : 돌릴 원판 숫자, x의 배수의 원판들을 돌린다.
 * d : 돌리는 방향 (0 : 시계방향, 1 : 반시계방향)
 * k : 돌리는 횟수
 */
void rotate(int xi, int di, int ki){
    int cnt=1;
    int x = xi*cnt;
    int d = di;
    int k = ki;
    vector<int> temp;
    while(x<=N){
        temp.clear();
        //어차피 M 번 탐색해서 반대방향인 경우 k 를 m-k 로 바꾸고 하면 똑같은 코드로 실행가능
        //반시계방향으로 동작하도록 구현
        if(d==0) k = M-ki;
        for(int i=k;i<M;i++) temp.push_back(map[x][i]);
        for(int i=0;i<k;i++) temp.push_back(map[x][i]);
        map[x]=temp;
        x = xi*(++cnt);
    }
}

/* 
 * 1. 인접하면서 같은 수 지우기
 * 2. 1이 아닌 경우 원판의 수의 평균 구해서 조정
 */
void update(){
    del_flag = false;
    int sum=0;
    int non_zero_cnt=0;
    for(int i=1;i<=N;i++){
        for(int j=0;j<M;j++){
            if(map[i][j]!=0) {
                sum+=map[i][j];
                non_zero_cnt++;
                BFS(i,j);
            }
        }
    }

    //1 진행했는데 del_flag 가 아직 false 라면 지워진 것이 없는 것이다. (BFS 내부에서 체크)
    //따라서 2 를 진행한다.
    
    //만약 위의 BFS 진행 시 변경이 있었다면 해당 조건문이 실행되지 않는다.
    //변경이 되지 않았을 경우 BFS를 통한 변화가 없기 때문에
    //위의 이중 for 문에서 얻은 sum, cnt 값을 이용해도 문제가 없다 (중복되는 탐색 제거)
    if(!del_flag){
        double avg;
        if(non_zero_cnt==0) avg=0;
        else avg = (double)sum/non_zero_cnt;
        for(int i=1;i<=N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j]!=0) {
                    if(map[i][j]>avg) map[i][j]--;
                    else if(map[i][j]<avg) map[i][j]++;
                }
            }
        }
    }

}

void solve(){
    for(int i=0;i<T;i++){
        if(remain_nums==0) break;
        int x,d,k;
        x=v[i].x;
        d=v[i].d;
        k=v[i].k;
        rotate(x,d,k);
        update();
    }

    int ans=0;
    for(int i=1;i<=N;i++){
        for(int j=0;j<M;j++){
            ans+=map[i][j];
        }
    }

    cout << ans;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    Input();
    solve();
    return 0;
}

 

 

결과 및 후기

코드가 길고 복잡해 보이지만 하나씩 나누어 확인하면 생각보다 간단한 것을 확인할 수 있다. 나름 중복을 피하며 시간을 많이 소모하지 않게 짠 것 같아 만족스러웠다.