주뇽's 저장소

백준(BOJ) Implement 마법사 상어와 비바라기 (21610) - GOLD5 본문

알고리즘/Implement

백준(BOJ) Implement 마법사 상어와 비바라기 (21610) - GOLD5

뎁쭌 2023. 10. 11. 21:23
728x90
반응형

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

 

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

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기

www.acmicpc.net

문제

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.

격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.

비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

  1. 모든 구름이 di 방향으로 si칸 이동한다.
  2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
  3. 구름이 모두 사라진다.
  4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
    • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
    • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
  5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

입력

첫째 줄에 N, M이 주어진다.

둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.

다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.

출력

첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.

제한

  • 2 ≤ N ≤ 50
  • 1 ≤ M ≤ 100
  • 0 ≤ A[r][c] ≤ 100
  • 1 ≤ di ≤ 8
  • 1 ≤ si ≤ 50

예제 입력 1 

5 4
0 0 1 0 2
2 3 2 1 0
4 3 2 9 0
1 0 2 9 0
8 8 2 1 0
1 3
3 4
8 1
4 8

예제 출력 1 

77
 

문제 해결

이제 골드 구현문제는 어느정도 감이 잡혔다. 기본적으로 골드5까지는 복잡한 알고리즘 없이 완전탐색으로 문제를 해결할 수 있다면 어렵지 않게 해결이 가능한것 같다. 

 

STEP1 : 8방향으로 이동

이 부분은 좀 브루트포스 방식으로 단순하게 구현했다. 일단 문제와 같이 인덱스를 1번부터 시작하기 위해서 주어진 크기보다 1칸 더 큰 배열을 생성한 후 왼쪽, 오른쪽, 위, 아래 부분만 구현하고 대각은 이미 구현한 코드를 이용했다. 예를 들어 왼쪽 대각선의 경우 왼쪽이동 함수와 위쪽 이동함수를 사용하면 된다.

void move_left(ll n){
    vector<vector<ll> >temp(n+1, vector<ll>(n+1, 0));
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] == 1){
                biba[i][j] = 0;
                ll tmp = j-1;
                if(tmp<=0){ //넘어가는 경우
                    tmp = n;
                }
                temp[i][tmp] = 1;
            }
        }
    }
    biba = temp;
}

void move_right(ll n){
    vector<vector<ll> >temp(n+1, vector<ll>(n+1, 0));
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] == 1){
                biba[i][j] = 0;
                ll tmp = j+1;
                if(tmp>n){ //넘어가는 경우
                    tmp = 1;
                }
                temp[i][tmp] = 1;
            }
        }
    }
    biba = temp;
}



void move_up(ll n){
    vector<vector<ll> >temp(n+1, vector<ll>(n+1, 0));
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] == 1){
                biba[i][j] = 0;
                ll tmp = i-1;
                if(tmp<=0){ //넘어가는 경우
                    tmp = n;
                }
                temp[tmp][j] = 1;
            }
        }
    }
    biba = temp;
}

void move_down(ll n){
    vector<vector<ll> >temp(n+1, vector<ll>(n+1, 0));
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] == 1){
                biba[i][j] = 0;
                ll tmp = i+1;
                if(tmp>n){ //넘어가는 경우
                    tmp = 1;
                }
                temp[tmp][j] = 1;
            }
        }
    }
    biba = temp;
}


void move_bibaragi(ll dir, ll number, ll n){
    if(dir == 1){ // 왼쪽 이동
        for(ll i=0; i<number; i++){
            move_left(n);
        }
    }
    else if(dir == 2){ // 왼쪽위대각
        for(ll i=0; i<number; i++){
            move_left(n);
            move_up(n);
        }
    }
    else if(dir == 3){ // 위
        for(ll i=0; i<number; i++){
            move_up(n);
        }
    }
    else if(dir == 4){ // 오른쪽위대각
        for(ll i=0; i<number; i++){
            move_right(n);
            move_up(n);
        }
    }
    
    else if(dir == 5){ // 오른쪽
        for(ll i=0; i<number; i++){
            move_right(n);
        }
    }
    else if(dir == 6){ // 오른쪽아래대각
        for(ll i=0; i<number; i++){
            move_right(n);
            move_down(n);
        }
    }
    else if(dir == 7){ // 아래
        for(ll i=0; i<number; i++){
            move_down(n);
        }
    }
    else{
        for(ll i=0; i<number; i++){
            move_left(n);
            move_down(n);
            
        }
    }
}

STEP2.  구름이 있는 칸에 바구니들의 물을 1개씩 증가하면 된다. 이건 단순하게 완전탐색을 이용해서 구현하면 된다.

void water(ll n){
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] == 1){ // 구름이 있는 칸
                Map[i][j]++;
            }
        }
    }
}

STEP3. 구름이 있던 칸에 대각선을 확인하여 물이 있다면 그 갯수만큼 해당 위치에 물의 양을 증가시켜야 한다. 이 부분은 인덱스 범위만 체크하면된다. 이동과는 다르게 이 부분은 인덱스를 초과하면 다음 인덱스로 넘어가지 않는다.

void copy_water(ll n){
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            ll cnt = 0;
            if(biba[i][j] == 1){ // 구름이 있는 칸
                for(ll k=0; k<4; k++){
                    ll nx = j + dx[k];
                    ll ny = i + dy[k];
                    if(index_check(nx, ny, n) == true && Map[ny][nx] >0){
                        cnt++;
                    }
                }
                Map[i][j] = Map[i][j] + cnt;
            }
        }
    }
}

STEP4. 기존에 있던 구름을 삭제하고 구름이 없던 칸에서 바구니의 물이 2개 이상이라면 물 2개를 이용해서 구름을 만든다.

void make_cloud(ll n){
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] != 1 && Map[i][j] >= 2){ // 구름이 없던 칸에는 구름을 만들기
                biba[i][j] = 1;
                Map[i][j] = Map[i][j]-2; 
            }
            else{ // 구름이 있던 칸에는 구름 제거
                biba[i][j] = 0;
            }
        }
    }
}

STEP5. 위의 STEP1 ~ STEP4의 반복이 모두 끝나면 해당 모든 칸에 있는 물의 양을 구해주면 된다.

ll get_water(ll n){
    ll answer = 0;
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            answer += Map[i][j];
        }
    }
    return answer;
}

 

전체 코드

#include <iostream>
#include <vector>
#define MAX_MAP_SZ 51

using namespace std;

typedef long long ll;

// //왼대위,  오대위, 오대아, , 왼대아
ll dx[4] = {-1, 1, 1, -1};
ll dy[4] = {-1, -1, 1, 1};

vector<vector<ll> >Map(MAX_MAP_SZ, vector<ll>(MAX_MAP_SZ, 0));
vector<vector<ll> >biba(MAX_MAP_SZ, vector<ll>(MAX_MAP_SZ, 0));

void init(ll N){
    for(ll i=1; i<=N; i++){
        for(ll j=1; j<=N; j++){
            cin >> Map[i][j];
        }
    }


    biba[N-1][1] = 1; biba[N-1][2] = 1;
    biba[N][1] = 1; biba[N][2] = 1;

}

void print(ll N, string str){
    if(str == "map"){
        for(ll i=1; i<=N; i++){
            for(ll j=1; j<=N; j++){
                cout << Map[i][j] << " ";
            }
        cout << "\n";
        }
    }
    else{
        for(ll i=1; i<=N; i++){
            for(ll j=1; j<=N; j++){
                cout << biba[i][j] << " ";
            }
            cout << "\n";
        }
    }
    
}

void move_left(ll n){
    vector<vector<ll> >temp(n+1, vector<ll>(n+1, 0));
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] == 1){
                biba[i][j] = 0;
                ll tmp = j-1;
                if(tmp<=0){ //넘어가는 경우
                    tmp = n;
                }
                temp[i][tmp] = 1;
            }
        }
    }
    biba = temp;
}

void move_right(ll n){
    vector<vector<ll> >temp(n+1, vector<ll>(n+1, 0));
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] == 1){
                biba[i][j] = 0;
                ll tmp = j+1;
                if(tmp>n){ //넘어가는 경우
                    tmp = 1;
                }
                temp[i][tmp] = 1;
            }
        }
    }
    biba = temp;
}



void move_up(ll n){
    vector<vector<ll> >temp(n+1, vector<ll>(n+1, 0));
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] == 1){
                biba[i][j] = 0;
                ll tmp = i-1;
                if(tmp<=0){ //넘어가는 경우
                    tmp = n;
                }
                temp[tmp][j] = 1;
            }
        }
    }
    biba = temp;
}

void move_down(ll n){
    vector<vector<ll> >temp(n+1, vector<ll>(n+1, 0));
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] == 1){
                biba[i][j] = 0;
                ll tmp = i+1;
                if(tmp>n){ //넘어가는 경우
                    tmp = 1;
                }
                temp[tmp][j] = 1;
            }
        }
    }
    biba = temp;
}


void move_bibaragi(ll dir, ll number, ll n){
    if(dir == 1){ // 왼쪽 이동
        for(ll i=0; i<number; i++){
            move_left(n);
        }
    }
    else if(dir == 2){ // 왼쪽위대각
        for(ll i=0; i<number; i++){
            move_left(n);
            move_up(n);
        }
    }
    else if(dir == 3){ // 위
        for(ll i=0; i<number; i++){
            move_up(n);
        }
    }
    else if(dir == 4){ // 오른쪽위대각
        for(ll i=0; i<number; i++){
            move_right(n);
            move_up(n);
        }
    }
    
    else if(dir == 5){ // 오른쪽
        for(ll i=0; i<number; i++){
            move_right(n);
        }
    }
    else if(dir == 6){ // 오른쪽아래대각
        for(ll i=0; i<number; i++){
            move_right(n);
            move_down(n);
        }
    }
    else if(dir == 7){ // 아래
        for(ll i=0; i<number; i++){
            move_down(n);
        }
    }
    else{
        for(ll i=0; i<number; i++){
            move_left(n);
            move_down(n);
            
        }
    }
}

void water(ll n){
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] == 1){ // 구름이 있는 칸
                Map[i][j]++;
            }
        }
    }
}

bool index_check(ll x, ll y, ll sz){
    if(x <= 0 || x > sz)
        return false;
    if(y <= 0 || y > sz)
        return false;
    return true;
}

void copy_water(ll n){
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            ll cnt = 0;
            if(biba[i][j] == 1){ // 구름이 있는 칸
                for(ll k=0; k<4; k++){
                    ll nx = j + dx[k];
                    ll ny = i + dy[k];
                    if(index_check(nx, ny, n) == true && Map[ny][nx] >0){
                        cnt++;
                    }
                }
                Map[i][j] = Map[i][j] + cnt;
            }
        }
    }
}

void make_cloud(ll n){
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            if(biba[i][j] != 1 && Map[i][j] >= 2){ // 구름이 없던 칸에는 구름을 만들기
                biba[i][j] = 1;
                Map[i][j] = Map[i][j]-2; 
            }
            else{ // 구름이 있던 칸에는 구름 제거
                biba[i][j] = 0;
            }
        }
    }
}

ll get_water(ll n){
    ll answer = 0;
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            answer += Map[i][j];
        }
    }
    return answer;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt" ,"r" ,stdin);

    ll N = 0; ll M = 0; ll dir, number;
    cin >> N >> M;
    init(N); 
    // init 바구니 셋팅 + 비바라기 시전
    
    for(ll i=0; i<M; i++){
        cin >> dir >> number;
        // step1. 8방향으로 이동
        move_bibaragi(dir, number, N);
        // step2. 구름이 있는 칸에 물 증가
        water(N);
        // step3. 구름이 있던 칸에 대각선에 물이 존재하면 그 갯수만큼 해당 물복사
        copy_water(N);
        // step4. 기존에 구름이 있던 칸을 제외하고 나머지 칸 중 물이 2개 이상이라면 구름 생성
        make_cloud(N);
    }
    // step5. 바구니에 있는 총 물의 양 구하기
    cout << get_water(N) << "\n";
    return 0;
}

코드가 상당히 길다. 하지만 구현문제는 우선적으로 Step을 나눠서 문제를 해결하는 방법으로 접근하는게 좋은것 같다. 코드 간소화는 그 이후에 해도 늦지 않다고 생각한다!

저작자표시

'알고리즘 > Implement' 카테고리의 다른 글

코드트리 Implement 정육면체 한번 더 굴리기 - GOLD3  (0) 2023.10.12
백준(BOJ) Implement 컨베이어 벨트 위의 로봇(20055) - GOLD5  (0) 2023.10.10
백준(BOJ) Implement 톱니바퀴(14891) - GOLD5  (0) 2023.10.09
'알고리즘/Implement' Related Articles more