[백준 21610][C++] 마법사 상어와 비바라기

문제

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

21610번: 마법사 상어와 비바라기

 

 

풀이 과정

1. 구름을 이동시키는 함수 구현 (이동 후 좌표 설정 방법은 마법사 상어와 파이어볼 문제와 동일 [문제] [풀이 및 소스코드])

2. 구름 위치에 물의 양을 늘리는 함수 구현 (이후 구름이 사라진다고 했지만, 구름 위치 정보 보존해야 한다)

3. 물의 양이 증가한 각 칸에 대해서 대각선을 탐색하고 그 수만큼 칸의 물을 증가시키는 함수 구현

4. 새로운 구름을 만드는 함수 구현

5. 입력받은 방향과 속도를 이용해, 1-4 과정을 반복한 뒤 최종 물의 양의 합을 구하여 출력한다.

 

 

 

세부 풀이

(1) init_cloud 함수, move_cloud 함수

구름을 이동시킬 새로운 좌표를 나머지(%) 연산을 통해서 구한다. 이때 움직인 구름과 이동한 구름이 겹치지 않게 새로운 배열을 만들어 구름을 이동시켰다. 

 

(2) rain 함수

문제의 3번 조건에서 '구름이 모두 사라진다' 고 되어있다. 하지만 구름 정보는 새로운 구름이 만들어지기 전까지 보존해야 한다. 비를 내리는 rain 함수, 물복사 버그 마법뿐만 아니라 새로운 구름을 만들 때도 이전의 구름의 정보가 필요하다.

현재 구름이 위치한 좌표에 물의 양을 하나씩 늘려준다.

 

(3) water_magic 함수

구름이 있던 위치를 방문한다. 각 위치에서 4방향의 대각선 위치를 탐색하고 물이 있었던 칸의 수만큼 해당 위치의 물의 양을 증가시킨다.

 

(4) new_cloud 함수

모든 map을 탐색하며 물의 양이 2 이상인 칸이며 이전 구름이 있던 자리가 아닌 칸에 새롭게 구름을 생성한다.

 

(5) solve 함수

입력받았던 d, s 값을 이용하여 move_cloud, rain, water_magic, new_cloud 함수를 순차적으로 수행한다.

해당 과정을 입력받았던 d, s 쌍의 수만큼 반복한 뒤 최종 map에 저장되어있는 물의 양의 합을 출력한다.

 

소스 코드

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

int N, M;
const int max_n = 51;
int map[max_n][max_n];
bool cloud[max_n][max_n];
int dir[9][2]={{0,0},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1}};
int moving_list[101][2];

void Input(){
    cin >> N >> M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin >> map[i][j];
        }
    }

    int d,s;
    for(int i=0;i<M;i++){
        cin >> d >> s;
        moving_list[i][0] = d;
        moving_list[i][1] = s;
    }
}

void init_cloud(){
    memset(cloud, false, sizeof(cloud));
    cloud[N][1]=true;
    cloud[N][2]=true;
    cloud[N-1][1]=true;
    cloud[N-1][2]=true;
}

void move_cloud(int d, int s){
    int speed = s%N;
    bool copy_cloud[max_n][max_n];
    memset(copy_cloud,false, sizeof(copy_cloud));

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(cloud[i][j]){
                int nx, ny;
                nx = (i + dir[d][0]*speed+N)%N;
                ny = (j + dir[d][1]*speed+N)%N;
                if(nx == 0) nx = N;
                if(ny == 0) ny = N;
                copy_cloud[nx][ny]=true;
            }
        }
    }

    memcpy(cloud, copy_cloud, sizeof(cloud));
}

void rain(){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(cloud[i][j]){
                map[i][j]++;
            }
        }
    }
}

void water_magic(){
    int plus_map[max_n][max_n];
    memset(plus_map,0,sizeof(plus_map));
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(!cloud[i][j]) continue;
            for(int k=2;k<=8;k+=2){
                int nx = i + dir[k][0];
                int ny = j + dir[k][1];
                if(nx < 1 || nx > N || ny < 1 || ny > N) continue;
                if(map[nx][ny]!=0) plus_map[i][j]++;
            }
        }
    }

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

void new_cloud(){
    bool new_cloud[max_n][max_n];
    memset(new_cloud, false, sizeof(new_cloud));
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(cloud[i][j] || map[i][j] <2) continue;
            new_cloud[i][j]=true;
            map[i][j]-=2;
        }
    }

    memcpy(cloud, new_cloud, sizeof(cloud));
}

void solve(){
    init_cloud();
    for(int i=0; i<M; i++){
        move_cloud(moving_list[i][0], moving_list[i][1]);
        rain();
        water_magic();
        new_cloud();
    }

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    Input();
    solve();
    return 0;
}

 

결과 및 후기

과정은 길었지만 구현은 간단한 문제였다. 입출력의 동기화를 끊는 sync_with_stdio, cin.tie를 이용하여 시간을 절감했다.