[백준/구현/C++] 21610번 마법사 상어와 비바라기 (삼성 SW 역량 테스트 기출)

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

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

문제 해결 방법

먼저 구조체 두개를 선언한다

MOVEINFO 는 구름 이동방향과 거리를 담고

POSITION에는 각 위치마다 현재 구름이 있는지 여부, 사라졌는지 여부, 물의양을 담는다

struct MOVEINFO{
    int dir; // 방향
    int sp; // 거리
};

struct POSITION{
    bool hasCloud = false; // 현재 구름 있는 경우
    bool disCloud = false; // 구름이 사라진 경우
    int water = 0;
};

그리고 필요한 변수들을 선언하고 입력받는다

int n, m;
POSITION pos[51][51];
MOVEINFO info[101];
queue<pair<int, int>> cloud; // 현재 구름 좌표

// 1~8 구름 이동 방향
pair<int, int> direct[9] = {{0,0},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1}};
int dx[] = {-1, -1, 1, 1}; // 대각선 방향
int dy[] = {-1, 1, -1, 1};

void input(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> pos[i][j].water;
        }
    }
    for(int i=0; i<m; i++){
        cin >> info[i].dir >> info[i].sp;
    }
    pos[n][1].hasCloud = true;
    cloud.push({n,1});
    pos[n][2].hasCloud = true;
    cloud.push({n,2});
    pos[n-1][1].hasCloud = true;
    cloud.push({n-1,1});
    pos[n-1][2].hasCloud = true;
    cloud.push({n-1,2});
}

구름이 이동할 때 주의해야 할 점은 나는 구름을 queue에 담아서 하나씩 pop을 해줬는데 그때마다 queue의 size가 작아져서 for문을 돌릴때 아예 변수로 따로 선언하고 시작했다

그리고 이동거리가 n보다 클 경우 n을 한번만 더하거나 빼도 0보다 작거나 n보다 큰 경우가 있다

그래서 거리를 n으로 나눈 나머지 거리만큼만 이동하도록 했다

int dir = info[i].dir; // 방향
int sp = info[i].sp%n; // 거리

// 구름 이동
int cloudSize = cloud.size();
for(int c=0; c<cloudSize; c++){
    int x = cloud.front().first; // 구름 좌표
    int y = cloud.front().second;
    int mx = cloud.front().first + direct[dir].first*sp; // 구름 이동 좌표
    int my = cloud.front().second + direct[dir].second*sp;
    cloud.pop();
    pos[x][y].hasCloud = false;
    
    if(mx < 1) mx += n;
    else if(mx > n) mx -= n;
    if(my < 1) my += n;
    else if(my > n) my -= n;
    
    pos[mx][my].hasCloud = true;
    pos[mx][my].water++;
    cloud.push({mx,my}); // 구름 좌표 목록에 추가
}

물이 증가된 위치에 물복사버그 마법을 하는데

물이 증가된 위치 = 구름이 있던 위치 라서 구름 목록 cloud를 사용해서 대각선 위치 바구니를 탐색하고 pop해주었다

구름이 사라진 위치는 .hasCloud = false 를 해주고 .disCloud = true 처리를 해준다

// 구름있던 위치 물복사버그
int size = cloud.size();
for(int c=0; c<size; c++){
    int x = cloud.front().first; // 구름 좌표
    int y = cloud.front().second;
    cloud.pop();
    
    pos[x][y].disCloud = true; // 사라진 구름 표시
    pos[x][y].hasCloud = false;
    
    int count = 0;
    for(int k=0; k<4; k++){ // 대각선 바구니 탐색
        int nx = x + dx[k];
        int ny = y + dy[k];
        if(nx<=0 || nx>n || ny<=0 || ny>n) continue;
        if(pos[nx][ny].water > 0) count++;
    }
    pos[x][y].water += count;
}

그리고 전체 공간을 돌면서 구름이 사라진 칸을 제외하고(disCloud 사용) 물이 2인 바구니를 탐색한다

// 구름 있던 칸 제외 바구니에 물 2이상이면 구름 생기고 물-2
for(int a=1; a<=n; a++){
    for(int b=1; b<=n; b++){
    
        if(pos[a][b].disCloud){ // 구름이 사라진 경우 통과
            pos[a][b].disCloud = false;
            continue;
        } else if(pos[a][b].water >= 2){ // 물이 2이상인 경우
            pos[a][b].hasCloud = true;
            cloud.push({a,b});
            pos[a][b].water -= 2;
        }
        
    }
}

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

struct MOVEINFO{
    int dir;
    int sp;
};

struct POSITION{
    bool hasCloud = false;
    bool disCloud = false;
    int water = 0;
};

int n, m;
POSITION pos[51][51];
MOVEINFO info[101];
queue<pair<int, int>> cloud; // 현재 구름 좌표

// 구름 이동 방향
pair<int, int> direct[9] = {{0,0},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1}};
int dx[] = {-1, -1, 1, 1}; // 대각선 방향
int dy[] = {-1, 1, -1, 1};

void input(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> pos[i][j].water;
        }
    }
    for(int i=0; i<m; i++){
        cin >> info[i].dir >> info[i].sp;
    }
    pos[n][1].hasCloud = true;
    cloud.push({n,1});
    pos[n][2].hasCloud = true;
    cloud.push({n,2});
    pos[n-1][1].hasCloud = true;
    cloud.push({n-1,1});
    pos[n-1][2].hasCloud = true;
    cloud.push({n-1,2});
}

void biba(){

    for(int i=0; i<m; i++){ // m번 이동
        int dir = info[i].dir; // 방향
        int sp = info[i].sp%n; // 거리

        // 구름 이동
        int cloudSize = cloud.size();
        for(int c=0; c<cloudSize; c++){
            int x = cloud.front().first; // 구름 좌표
            int y = cloud.front().second;
            int mx = cloud.front().first + direct[dir].first*sp; // 구름 이동 좌표
            int my = cloud.front().second + direct[dir].second*sp;
            cloud.pop();
            pos[x][y].hasCloud = false;

            if(mx < 1) mx += n;
            else if(mx > n) mx -= n;
            if(my < 1) my += n;
            else if(my > n) my -= n;

            pos[mx][my].hasCloud = true;
            pos[mx][my].water++;
            cloud.push({mx,my}); // 구름 좌표 목록에 추가
        }

        // 구름있던 위치 물복사버그
        int size = cloud.size();
        for(int c=0; c<size; c++){
            int x = cloud.front().first; // 구름 좌표
            int y = cloud.front().second;
            cloud.pop();
            pos[x][y].disCloud = true; // 사라진 구름 표시
            pos[x][y].hasCloud = false;

            int count = 0;
            for(int k=0; k<4; k++){ // 대각선 바구니 탐색
                int nx = x + dx[k];
                int ny = y + dy[k];

                if(nx<=0 || nx>n || ny<=0 || ny>n) continue;
                if(pos[nx][ny].water > 0) count++;
            }
            pos[x][y].water += count;
        }

        // 구름 있던 칸 제외 바구니에 물 2이상이면 구름 생기고 물-2
        for(int a=1; a<=n; a++){
            for(int b=1; b<=n; b++){

                if(pos[a][b].disCloud){
                    pos[a][b].disCloud = false;
                    continue;
                } else if(pos[a][b].water >= 2){
                    pos[a][b].hasCloud = true;
                    cloud.push({a,b});
                    pos[a][b].water -= 2;
                }

            }
        }

    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    biba();

    int result = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            result += pos[i][j].water;
        }
    }
    cout << result;

    return 0;
}