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

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

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

 

최종 코드

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

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

//
//  main.cpp
//  BJ21610_1
//
//  Created by Hwayeon on 2021/10/15.
//

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

int N, M;
int A[51][51] = {0, };

//cmds[i] = {d, s};
vector<pair<int, int>> cmds;
vector<pair<int, int>> clouds;
vector<pair<int, int>> new_clouds;

int dr[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
int dc[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};

void move_clouds(int d, int s){
    int cr, cc;
    for(int i=0; i<clouds.size(); i++){
        cr = clouds[i].first;
        cc = clouds[i].second;
        for(int ss=0; ss<s; ss++){
            cr += dr[d];
            cc += dc[d];
            if(cr == N+1) cr = 1;
            else if(cr == 0) cr = N;
            if(cc == N+1) cc = 1;
            else if(cc == 0) cc = N;
        }
        clouds[i].first = cr;
        clouds[i].second = cc;
    }
}

void play_bug_copy_water(){
    int r, c;
    int cnt = 0;
    for(int i=0; i<clouds.size(); i++){
        r = clouds[i].first;
        c = clouds[i].second;
        cnt = 0;
        for(int d=2; d<=8; d+=2){
            int nr = r+dr[d];
            int nc = c+dc[d];
            if(nr<=0 || nr>N || nc<=0 || nc>N) continue;
            if(A[nr][nc] > 0) cnt++;
        }
        A[r][c] += cnt;
    }
}

void make_new_clouds(){
    new_clouds.clear();
    bool check = true;
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++){
            if(A[r][c] >= 2){
                check = true;
                for(int i=0; i<clouds.size(); i++){
                    if(clouds[i].first == r && clouds[i].second == c){
                        check = false;
                        break;
                    }
                }
                if(!check) continue;
                new_clouds.push_back({r, c});
                A[r][c] -= 2;
            }
        }
    }
    clouds = new_clouds;
}

void play_bibaragi(){
    for(int cmd=0; cmd<M; cmd++){
        //1. 구름 이동
        move_clouds(cmds[cmd].first, cmds[cmd].second);
        //2. 구름에서 비 내림
        for(int i=0; i<clouds.size(); i++){
            A[clouds[i].first][clouds[i].second]++;
        }
        //3. 물복사 버그
        play_bug_copy_water();
        //4. 새 구름 생성
        make_new_clouds();
    }
}

int get_sum_water(){
    int sum = 0;
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++){
            sum += A[r][c];
        }
    }
    return sum;
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++){
            cin >> A[r][c];
        }
    }
    int d, s;
    for(int i=0; i<M; i++){
        cin >> d >> s;
        cmds.push_back({d, s});
    }
    //비구름 초기화
    clouds.push_back({N, 1});
    clouds.push_back({N, 2});
    clouds.push_back({N-1, 1});
    clouds.push_back({N-1, 2});
    
    play_bibaragi();
    cout << get_sum_water() << endl;
    
    return 0;
}

---

풀이 과정

풀이 시간 37분

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

int N, M;
//1 <= r,c <= N
int A[51][51] = {0, };

//cmds[i] = {d, s};
vector<pair<int, int>> cmds;
//구름의 위치를 담는 벡터
vector<pair<int, int>> clouds;
//새로 생긴 구름의 위치를 담는 벡터
vector<pair<int, int>> new_clouds;

int dr[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
int dc[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};

void move_clouds(int d, int s){
    int cr, cc;
    //각각의 구름을 이동시킨다
    for(int i=0; i<clouds.size(); i++){
        cr = clouds[i].first;
        cc = clouds[i].second;
        for(int ss=0; ss<s; ss++){
            cr += dr[d];
            cc += dc[d];
            //행이 N+1이면 1로 바꿔준다 -> 1행과 N행은 연결되어 있다
            if(cr == N+1) cr = 1;
            //행이 0이면 N로 바꿔준다 -> 1행과 N행은 연결되어 있다
            else if(cr == 0) cr = N;
            //열이 N+1이면 1로 바꿔준다 -> 1열과 N열은 연결되어 있다
            if(cc == N+1) cc = 1;
            //열이 0이면 N으로 바꿔준다 -> 1열과 N열은 연결되어 있다
            else if(cc == 0) cc = N;
        }
        clouds[i].first = cr;
        clouds[i].second = cc;
    }
}

void play_bug_copy_water(){
    int r, c;
    int cnt = 0;
   	//각 구름의 위치에서 물복사버그가 일어난다
    for(int i=0; i<clouds.size(); i++){
        r = clouds[i].first;
        c = clouds[i].second;
        cnt = 0;
        //대각선 방향의 바구니 탐색
        for(int d=2; d<=8; d+=2){
            int nr = r+dr[d];
            int nc = c+dc[d];
            //범위를 벗어난 경우, 무시한다
            if(nr<=0 || nr>N || nc<=0 || nc>N) continue;
            //해당 바구니에 물이 있는 경우, 카운팅
            if(A[nr][nc] > 0) cnt++;
        }
        //대각선 방향의 물이 있는 바구니의 수만큼 (r, c) 위치의 바구니의 물의 양이 증가한다
        A[r][c] += cnt;
    }
}

void make_new_clouds(){
    new_clouds.clear();
    
    //check = true -> 해당 위치에 구름이 생성됨, check = false -> 해당 위치에 구름이 생성되지 않음
    bool check = true;
    
    //각 바구니를 탐색
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++){
        	//바구니의 물의 양이 2 이상인 경우,
            if(A[r][c] >= 2){
                check = true;
                //이전에 사라진 구름의 위치와 같은지 탐색
                for(int i=0; i<clouds.size(); i++){
                	//이전에 사라진 구름의 위치와 같은 경우, 구름이 생길 수 없다
                    if(clouds[i].first == r && clouds[i].second == c){
                        check = false;
                        break;
                    }
                }
                
                //구름이 생기지 않는 경우,
                if(!check) continue;
                
                //구름이 생기는 경우, new_clouds에 구름의 위치를 담고 해당 위치의 바구니의 물의 양은 2 감소한다
                new_clouds.push_back({r, c});
                A[r][c] -= 2;
            }
        }
    }
    //clouds를 업데이트한다
    clouds = new_clouds;
}

void play_bibaragi(){
    for(int cmd=0; cmd<M; cmd++){
        //1. 구름 이동 -> O(N^2)
        move_clouds(cmds[cmd].first, cmds[cmd].second);
        
        //2. 구름에서 비 내림 -> O(N^2)
        //각 구름의 위치에 있는 바구니에 물의 양이 1 증가한다
        for(int i=0; i<clouds.size(); i++){
            A[clouds[i].first][clouds[i].second]++;
        }
        
        //3. 물복사 버그 -> O(N^2)
        play_bug_copy_water();
        
        //4. 새 구름 생성 -> O(N^4)
        make_new_clouds();
    }
}

int get_sum_water(){
    int sum = 0;
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++){
            sum += A[r][c];
        }
    }
    return sum;
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++){
            cin >> A[r][c];
        }
    }
    int d, s;
    for(int i=0; i<M; i++){
        cin >> d >> s;
        cmds.push_back({d, s});
    }
    //비구름 초기화
    clouds.push_back({N, 1});
    clouds.push_back({N, 2});
    clouds.push_back({N-1, 1});
    clouds.push_back({N-1, 2});
    
    play_bibaragi();
    cout << get_sum_water() << endl;
    
    return 0;
}
//시간복잡도 = O(N^4), 공간복잡도 = O(N^2)

---

이전 풀이

풀이 시간 2시간 2분

//
//  main.cpp
//  BJ21610
//
//  Created by Hwayeon on 2021/08/10.
//

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

int N, M;

//바구니 위치별 물의 양을 담을 배열, 1 <= x, y <= N
int A[51][51] = {0, };

int dx[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int dy[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};

//이동 명령 cmd[i] = {d, s}
vector<pair<int, int>> cmd;

//비바라기 시전 비구름 초기화
deque<pair<int, int>> cloud = {{1, N}, {2, N}, {1, N-1}, {2, N-1}};

//3.과정에서 사라질 구름이 있는 바구니 위치를 담을 벡터
vector<pair<int, int>> basket;
int d, s;

void move_cloud(int c){
	//이동 명령의 방향과 거리 설정
    d = cmd[c].first;
    s = cmd[c].second;
    
    basket.clear();
    int nx, ny;
    //1. 모든 구름 d방향으로 s칸 이동 -> T(n) = cloud.size()
    while(!cloud.empty()){
    	//이동할 위치
        nx = cloud.front().first + dx[d] * s;
        ny = cloud.front().second + dy[d] * s;
        //경계값 넘었을 때 위치 찾아주기
        if(nx > N) nx %= N;
        if(nx < 1) nx += N*(abs(nx)/N+1);
        if(ny > N) ny %= N;
        if(ny < 1) ny += N*(abs(ny)/N+1);
        
        //2. 구름에서 비가 내려 바구니에 물의 양 1 증가 -> 증가한 바구니 위치 담기
        A[ny][nx] ++;
        basket.push_back({nx, ny});
        
        //3. 구름이 사라진다
        cloud.pop_front();
    }
    
    //4. 물복사버그 마법 -> T(n) = basket.size()*4
    for(int i=0; i<basket.size(); i++){
        int bx = basket[i].first;
        int by = basket[i].second;
        //대각선 방향 체크
        for(int dd = 2; dd <= 8; dd+=2){
            nx = bx + dx[dd];
            ny = by + dy[dd];
            //경계값, 물의 양 체크
            if(nx >= 1 && nx <= N && ny >= 1 && ny <= N && A[ny][nx] > 0){
                A[by][bx]++;
            }
        }
    }
    
    //5. 물의 양이 2 이상인 모든 칸에 구름 생성 -> 물의 양 -= 2, basket 벡터에 없는 위치에만 생성
    //T(n) = N^2 * basket.size()
    for(int y=1; y<=N; y++){
        for(int x=1; x<=N; x++){
            if(A[y][x]>=2){
                int ck = 1;
                for(int i=0; i<basket.size(); i++){
                	//사라진 구름 위치와 같은 경우
                    if(y==basket[i].second && x==basket[i].first){
                        ck = 0;
                        break;
                    }
                }
                //구름 생성
                if(ck){
                    A[y][x] -= 2;
                    cloud.push_back({x, y});
                }
            }
        }
    }
}

int cal_water(){
	//전체 물의 양 구하기
    int sum_w = 0;
    for(int y=1; y<=N; y++){
        for(int x=1; x<=N; x++){
            sum_w += A[y][x];
        }
    }
    return sum_w;
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    //바구니 위치별 물의 양 입력 받기
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> A[i][j];
        }
    }
    //이동 명령 cmd벡터에 담기
    for(int i=0; i<M; i++){
        cin >> d >> s;
        cmd.push_back({d, s});
    }
    //이동 명령 순서대로 구름 이동
    for(int i=0; i<cmd.size(); i++){
        move_cloud(i);
    }
    cout << cal_water() << endl;
    return 0;
}
//T(n) = M*(cloud.size()+ basket.size()*4 + N^2*basket.size()) -> basket.size()가 최약의 경우 N^2이 될 수 있다
//시간복잡도 = O(n^5), 공간복잡도 = O(n^2)