백준 20057번 - 마법사 상어와 토네이도

www.acmicpc.net/problem/20057

20057번: 마법사 상어와 토네이도

토네이도가 한칸 이동할때마다 흩날리는 모래를 격자에 업데이트하면서 정해진 범위밖으로 나간 모래의 총량을 계산하는 문제입니다.

구현해야 할 내용은 크게 두가지로 나눠볼 수 있습니다.

 

1. 토네이도 이동경로 인덱싱
2. 이동 방향에 따른 모래비율 맵핑

 

토네이도 이동경로

우선 토네이도 이동경로 인덱싱은 토네이도 시작점(N/2, N/2)을 기준으로

위치가 바뀌는 방향의 순서가 ← , ↓ , → , ↑ 이고 방향이 2번 바뀔때마다 이동하는 칸이 1씩 증가하는 규칙을 이용했습니다.

 

위의 그림의 화살표를 보면 빨간색 1칸, 노란색 2칸, 초록색 3칸으로 방향이 2번 바뀔때마다 이동하는 칸 수가 1씩 증가하는것을 확인할 수 있습니다.

 

흩날리는 모래 비율

흩날리는 모래는 x에서 y로 이동하는 방향에 따라 y의 모래를 위와 같은 비율로 분배해줘야 합니다.

가장 간단한 방법으로는 a를 포함하여 모래량이 변화될 10개의 좌표를 직접 맵핑해 주는 방법이 있지만,

해당 좌표에 마스크를 씌운다는 느낌으로 비율의 정보를 업데이트하는 방식을 사용했습니다.

문제에서 주어진 기본 비율정보를(코드에서 tmask) 회전하여 저장하고 이를 이동좌표마다 적용시키는 방법입니다.

 

이렇게 얻어진 비율정보 mask[5][5][방향] 를 방향에 따라 토네이도의 이동좌표에 적용시키고 격자 범위를 벗어난 모래를 누적하여 출력하면 정답을 얻을 수 있습니다.

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;

int N,sum=0;
int m[500][500]{};
int dy[4] = {0,1,0,-1};
int dx[4] = {-1,0,1,0};
int mask[5][5][4]{};
int tmask[5][5]={
    {0,0,2,0,0},
    {0,10,7,1,0},
    {5,0,0,0,0},
    {0,10,7,1,0},
    {0,0,2,0,0}
};

// mask의 비율정보에 따른 모래의 이동
void move(int cy, int cx, int d){
    int y=cy-2, x=cx-2;
    int remains = m[cy][cx];
    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            int ny = y + i;
            int nx = x + j;
            int ns = m[cy][cx] * mask[i][j][d] / 100;
            remains -= ns;
            if(ny<0 || nx<0 || ny>=N || nx>=N) {
                sum += ns;
                continue;
            }
            m[ny][nx] += ns;
        }
    }
	
    // 남은 모래들은 비율정보에서 a에 해당하는 좌표에 저장되어야 함
    int ny = cy + dy[d];
    int nx = cx + dx[d];
    if(ny<0 || nx<0 || ny>=N || nx>=N) {
        sum += remains;
        return;
    }
    m[ny][nx] += remains;
}

// 토네이도 이동
void tornado(){
    int cnt=1, idx = 1, dir=0, cy=N/2, cx=N/2;
    while(cnt < N*N){
        for(int i=0; i<2; i++){
            for(int k=0; k<idx; k++){
                int ny = cy + dy[dir];
                int nx = cx + dx[dir];
                move(ny, nx, dir);
                m[ny][nx] = cnt++;
                if(cnt>=N*N) return;
                cy = ny;
                cx = nx;
            }
            dir = (dir+1)%4;
        }
        idx++;
    }
}

// 마스크 정보 초기화
void initMask(int K){
	// mask[i][j][d]에서 d는 dy[4], dx[4]에서의 인덱스를 뜻함
	// 왼쪽 방향: d=0
    for(int i=0; i<K; i++){
        for(int j=0; j<K; j++){
            mask[i][j][0] = tmask[i][j];
        }
    }
    // 아래 방향: d=1
    for(int j=K-1,ii=0; j>=0,ii<K; j--,ii++){
        for(int i=0,jj=0; i<K,jj<K; i++,jj++){
            mask[ii][jj][1] = tmask[i][j];
        }
    }
    // 오른쪽 방향: d=2
    for(int i=K-1,ii=0; i>=0,ii<K; i--,ii++){
        for(int j=K-1,jj=0; j>=0,jj<K; j--,jj++){
            mask[ii][jj][2] = tmask[i][j];
        }
    }
    // 위 방향: d=3
    for(int j=0,ii=0; j<K,ii<K; j++,ii++){
        for(int i=K-1,jj=0; i>=0,jj<K; i--,jj++){
            mask[ii][jj][3] = tmask[i][j];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>m[i][j];
        }
    }
    
    initMask(5);
    tornado();
    cout<<sum;
}