[BOJ] 마법사 상어와 토네이도 20057번 C++

문제

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

 

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

 

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

 

입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다.

 

접근 방식

 

오랜만에 승부욕을 불러 일으켰던 문제다..

분명 복잡해 보이지만 풀만하다고 생각했는데 생각보다 오래걸려서 풀었다...!

 

풀이 방법은 다음과 같다.

 

1. 토네이도 방향에 맞는 이동식 구하기

먼저 토네이도는 좌 - 하 - 우 - 상 의 방향으로 반복하기 때문에

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

 

 이러한 순서로 배열을 만들어 주었다

 

또한, 토네이도는 1-1-2-2-3-3-4-4-... 이런식으로 각 숫자마다 두번씩 반복하기 때문에

가운데 좌표부터 시작해서

1번부터 두번씩 반복할 수 있게 해주었다

이 때, 숫자만큼 이동하기 때문에 숫자만큼 반복문으로 한 칸씩 토네이도가 방문할 수 있도록 해주었다

그리고 그 방문이 끝나면 방향 순서를 증감해주어서 좌 - 하 - 우 - 상 순서로 계속해서 반복할 수 있도록 해주었다.

int x = N/2 + 1; int y = N/2 + 1;
    for(int i=1; i<=N; i++) {
        int cnt = 2;
        while(cnt--) {
            for(int j=0; j<i; j++) {
                x = x + dx[direction%4];
                y = y + dy[direction%4];
                spread(x,y,direction%4);
            }
            direction++;

        }
    }

 

 

2. 모래가 흩날리는 비율 구하기

모래는 다음과 같이 흩날린다. 이때, y좌표를 기준으로 각 비율의 자릿값을 구해주면 된다

또한, 토네이도의 방향에 바뀌면 각 비율의 자리가 바뀌기 때문에

좌 - 하 - 우 - 상 순서로 각 비율의 좌표 이동값을 구해주었다.

 

float sandRatio[9] = {1,1,2,2,7,7,10,10,5};
int spreadX[4][9] = {{-1,1,-2,2,-1,1,-1,1,0},{-1,-1,0,0,0,0,1,1,2},{-1,1,-2,2,-1,1,-1,1,0},{1,1,0,0,0,0,-1,-1,-2}};
int spreadY[4][9] = {{1,1,0,0,0,0,-1,-1,-2},{-1,1,-2,2,-1,1,-1,1,0},{-1,-1,0,0,0,0,1,1,2},{1,-1,2,-2,1,-1,1,-1,0}};

 

sandRatio는 각 좌표의 모래 비율이다

꽤나 노가다 형식으로 구했지만, 다른 블로그 풀이들을 참고하니 오히려 헷갈려서 그냥 순수 다 대입하면서 구했다!

 

3. 모래 이동시키기

 

1번에서 구한 이동식으로 모래를 흩날리면 된다

이때 순서는

1. 9개의 비율을 반복문으로 돌면서 각 좌표에 해당하는 모래값 구하기, 움직이는 모래의 총량에 모래값 더하기

2. 만약 좌표가 격자 밖을 나가면 해당 모래값은 결과값에 저장하기

3. 원래 모래의 값에서 움직인 모래의 총값 빼서 'a' 좌표에 더하기. 만약, 이때 a좌표가 격자 밖이라면 결과값에 더하기

 

 

간단하지만 복잡한 문제였다..!

 

코드

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

int N, direction = 0, ans = 0;
int mat[505][505];
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
float sandRatio[9] = {1,1,2,2,7,7,10,10,5};
int spreadX[4][9] = {{-1,1,-2,2,-1,1,-1,1,0},{-1,-1,0,0,0,0,1,1,2},{-1,1,-2,2,-1,1,-1,1,0},{1,1,0,0,0,0,-1,-1,-2}};
int spreadY[4][9] = {{1,1,0,0,0,0,-1,-1,-2},{-1,1,-2,2,-1,1,-1,1,0},{-1,-1,0,0,0,0,1,1,2},{1,-1,2,-2,1,-1,1,-1,0}};

void spread(int x, int y, int d) {
    int totalSand = mat[x][y];
    mat[x][y] = 0;
    int totalMovedSand = 0;
    
    if(totalSand == 0) return;

    for(int i=0; i<9; i++) {
        int nx = x + spreadX[d][i];
        int ny = y + spreadY[d][i];
        int moveSand = (totalSand * sandRatio[i]) / 100.0;
        totalMovedSand += moveSand;


        if(nx <= 0 || ny <= 0 || nx > N || ny > N) {
            ans += moveSand;
        }else mat[nx][ny] += moveSand;
        
    }

    int remainSand = totalSand - totalMovedSand;
    
    int ax = x + dx[d];
    int ay = y + dy[d];
    if(ax <= 0 || ay <= 0 || ax > N || ay > N) ans += remainSand;
    else mat[ax][ay] += remainSand;
}

int main() {
    cin>>N;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            cin>>mat[i][j];
        }
    }
    int x = N/2 + 1; int y = N/2 + 1;
    for(int i=1; i<=N; i++) {
        int cnt = 2;
        while(cnt--) {
            for(int j=0; j<i; j++) {
                x = x + dx[direction%4];
                y = y + dy[direction%4];
                spread(x,y,direction%4);
            }
            direction++;

        }
    }
    cout<<ans;

}