[C++][백준 20057] 마법사 상어와 토네이도

문제 설명은 더보기를 눌러주세요

문제링크 : www.acmicpc.net/problem/20057

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

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 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] 이다.

출력

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

제한

• 3 ≤ N ≤ 499
• N은 홀수
• 0 ≤ A[r][c] ≤ 1,000
• 가운데 칸에 있는 모래의 양은 0

 

-풀이-

1. 토네이도의 이동 과정을 보면, 
    1) 왼쪽으로 한 칸 -> 아래쪽으로 한 칸
    2) 오른쪽으로 두 칸 -> 위쪽으로 두 칸
    3) 왼쪽으로 세 칸 -> 아래쪽으로 세 칸
    4) 오른쪽으로 네 칸 -> 위쪽으로 네 칸... 
    이와 같이 아래 -> 오른쪽으로, 위 -> 왼쪽으로 방향을 바꿀 때, 칸수가 하나 증가한다.

2. 모래가 흩날리는 비율에 대한 5x5 sweepMap을 만들어서,
   방향에 따라 회전시켜가며 곱해주면 된다.(구현)

3. 토네이도가 이동하고 있는 자리는 무조건 0이 되기 때문에, 
    해당 자리에 있던 모래의 양 = 해당 위치에서 밖으로 나간 모래의 양 + 일정한 비율로 흩날리게 된 모래의 양임을
    기억하고 구현하면 된다. (자세한 내용은 주석 참고)    

 

-코드-

#include<iostream>
#include<algorithm>
using namespace std;
void move(int x, int y, int cnt, int limit, int dir);
void sweep(int x, int y, int dir);
int N, ans = 0;
int map[501][501];
int dx[] = {0, 0, 1, 0, -1};
int dy[] = {0, -1, 0, 1, 0};
int main(){
    cin >> N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> map[i][j];
        }
    }
    int sx = N/2+1, sy = N/2+1; // 중앙에서 시작
    move(sx, sy, 1, 1, 1);
    cout << ans;
}

void move(int x, int y, int cnt, int limit, int dir) {
    if(x == 1 && y == 1) return;
    int nx = x + dx[dir], ny = y + dy[dir];
    sweep(nx, ny, dir);
    if(cnt == limit) {
        if(dir == 1) move(nx, ny, 1, limit, dir+1); // 왼쪽 -> 아래쪽
        else if(dir == 2) move(nx, ny, 1, limit+1, dir+1); // 아래쪽 -> 오른쪽
        else if(dir == 3) move(nx, ny, 1, limit, dir+1); // 오른쪽 -> 위쪽
        else move(nx, ny, 1, limit+1, 1); // 위쪽 -> 왼쪽
    } else {
        move(nx, ny, cnt+1, limit, dir);
    }   
}

void sweep(int x, int y, int dir){ // 해당 위치와 방향
    int total = map[x][y], cnt = 0;
    int sweepMap[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}};
    map[x][y] = 0; // 해당 위치는 0으로 만듦.
    if(dir == 1) { // 왼쪽
        for(int i=0; i<5; i++){ 
            for(int j=0; j<5; j++){
                int nx = x-2+i, ny = y-2+j;
                cnt += (sweepMap[i][j] * total)/100;
                if(nx < 1 || ny < 1 || nx > N || ny > N) ans += (sweepMap[i][j] * total)/100; // 밖으로 나감
                else map[nx][ny] += (sweepMap[i][j] * total)/100; // 맵의 비율만큼 곱해서 더해줌.
            }
        }
        if(y-1 < 1) ans += (total-cnt); // 밖으로 나감
        else map[x][y-1] += (total-cnt); // a(나머지)를 더해줌
    } else if(dir == 2) { // 아래쪽
        for(int i=4; i>=0; i--){
            for(int j=0; j<5; j++){
                int nx = x-2+(4-i), ny = y-2+j;
                cnt += (sweepMap[j][i] * total)/100;
                if(nx < 1 || ny < 1 || nx > N || ny > N) ans += (sweepMap[j][i] * total)/100;
                else map[nx][ny] += (sweepMap[j][i] * total)/100;
            }
        }
        if(x+1 > N) ans += (total-cnt);
        else map[x+1][y] += (total-cnt);
    } else if(dir == 3) { // 오른쪽 
        for(int i=0; i<5; i++){
            for(int j=4; j>=0; j--){
                int nx = x-2+i, ny = y-2+(4-j);
                cnt += (sweepMap[i][j] * total)/100;
                if(nx < 1 || ny < 1 || nx > N || ny > N) ans += (sweepMap[i][j] * total)/100;
                else map[nx][ny] += (sweepMap[i][j] * total)/100;
            }
        }
        if(y+1 > N) ans += (total-cnt);
        else map[x][y+1] += (total-cnt);
    } else { // 위쪽
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                int nx = x-2+i, ny = y-2+j;
                cnt += (sweepMap[j][i] * total)/100;
                if(nx < 1 || ny < 1 || nx > N || ny > N) ans += (sweepMap[j][i] * total)/100;
                else map[nx][ny] += (sweepMap[j][i] * total)/100;
            }
        }
        if(x-1 < 1) ans += (total-cnt);
        else map[x-1][y] += (total-cnt);
    }
    return;
}