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

[문제]

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

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

 

[풀이]

전에 풀었던 삼성기출 문제 처럼 순서대로 구현하니 그리 어렵지 않았다.

그런데 오래걸린 알고리즘이... 구름이 상, 좌 방향으로 갈 시 - 좌표가 되었을때 처리하는 방법을 고민하는데 조금 시간이 걸렸다. +가 될때까지 while문으로 +N 만큼 증가시키는 방법을 사용했다.

구름의 대각선 방향움직임은 만들어놓은 상하좌우 움직임을 합쳐서 사용. 물복사 버그에서도 BFS의 대각선 방향응용을 해서 풀었는데, 이 두가지가 흥미로웠다.

 

[코드]

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int N, M;
int d, s;
int board[51][51];
vector <pair<int,int>> cloud;
bool vis[51][51];

void move(int dir, int step){
    if(dir == 1){ //좌
        for(int i = 0; i < cloud.size(); i++){
            cloud[i].Y -= step;
            while(cloud[i].Y < 0)
                cloud[i].Y += N;
        }
    }
    if(dir == 2){ //좌상
        move(1,step);
        move(3,step);
    }
    if(dir == 3){//상
        for(int i = 0; i < cloud.size(); i++){
            cloud[i].X -= step;
            while(cloud[i].X < 0)
                cloud[i].X += N;
        }
    }
    if(dir == 4){ //우상
        move(3,step);
        move(5,step);
    }
    if(dir == 5){//우
        for(int i = 0; i < cloud.size(); i++){
            cloud[i].Y += step;
            cloud[i].Y %= N;
        }
    }
    if(dir == 6){ //우하
        move(5,step);
        move(7,step);
    }
    if(dir == 7){//하
        for(int i = 0; i < cloud.size(); i++){
            cloud[i].X += step;
            cloud[i].X %= N;
        }
    }
    if(dir == 8){//좌하
        move(7,step);
        move(1,step);
    }
}

int dx[4] = {1,1,-1,-1};
int dy[4] ={1,-1,1,-1}; //우하, 좌하, 우상, 좌상

void bug (int x, int y){
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; //넘어간건 스킵
        if(board[nx][ny] != 0) board[x][y]++;
    }
}



int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }

    cloud.push_back({N - 1, 0});
    cloud.push_back({N - 1, 1});
    cloud.push_back({N - 2, 0});
    cloud.push_back({N - 2, 1}); //비바람 만들기..
    for(int k = 0; k < M; k++){ //M가지 이동
        for(int i = 0; i < N; i++){
            memset(vis[i],false,sizeof(vis[i]));
        }

        cin >> d >> s;

        move(d,s); //1. 비바람 이동
        for(int i = 0; i < cloud.size();i++) {
            board[cloud[i].X][cloud[i].Y] += 1; //2.비내리기
            vis[cloud[i].X][cloud[i].Y] = 1;
        }

        for(int i = 0; i < cloud.size();i++) {
            bug(cloud[i].X,cloud[i].Y); //3.물복사 버그
        }

        cloud.clear(); //구름 없어짐...
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] >= 2 && !vis[i][j]) {
                    cloud.push_back({i, j});
                    board[i][j] -= 2;
                }
            }
        }
    }

    int sum = 0;
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            sum+= board[i][j];
        }
    }
    cout << sum;


}

 

플레티넘이나 골드 상위문제는 풀기 겁나서... 낮은거부터 손대는중...