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

백준의 마법사 상어와 토네이도(20057) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

토네이도가 움직일 때, 특정 좌표의 모래의 양이 주변에 주어진 %만큼 흩날리게 되는데, 최종적으로 토네이도가 소멸된 후, 격자의 밖으로 나간 모래의 양을 구해야 하는 문제이다.

먼저, 토네이도의 움직임에 어떤 특징이 있는지부터 모래가 흩날리는 영역들에 대해서 처리하는 과정까지, 그리고 그 과정에서 정답을 도출하는 과정까지 진행해보자.

#1. 토네이도의 움직임

#1 - 1) 토네이도가 움직이는 칸 수

토네이도는 주어진 맵의 가장 한 가운데에서 시작해서 달팽이 모양(?)을 그리면서 진행하게 된다.

.

문제에 제시되어 있는 그림을 참고하면 토네이도는 위와 같은 방식으로 움직이게 된다.

지금부터는 진행방향과 진행방향에 따라 나아가는 칸 수에 따라서 토네이도의 움직임에 어떤 특징이 있는지 알아보자.

먼저, 토네이도가 가장 처음 시작하는 부분을 한번 보자.

토네이도가 가장 처음 시작하는 부분에서는 무조건적으로 "왼쪽"방향으로 진행한다는 것을 알 수 있다.

칸 수까지 한번 본다면, "왼쪽 방향으로 1칸 움직이는 움직임"을 가지고 있다.

그 후에 진행방향이 바뀌게 되고, 아래쪽으로 또 1칸 움직이게 된다.

지금까지 우리가 이야기한 토네이도의 움직임을 표시해 보면 다음과 같다.

.

빨강색 화살표로 표시한 것이 우리가 방금 이야기한 토네이도의 가장 첫 움직임과 두 번째 움직임이다.

첫 번째 움직임과 두 번째 움직임을 보면, "토네이도는 한 칸 움직이는 행위를 2번 한다." 라는 것을 알 수 있다.

그 다음 움직임을 한번 보자.

그 다음 움직임에서는 또 방향이 바뀐채로, 이번에는 2칸씩 나아가게 된다.

2칸씩 나아간 후에는, 또 방향이 바뀐채로, 2칸씩 한번 더 나아가게 된다. 맵에 표시해보면 다음과 같다.

.

우리가 방금 이야기한 움직임이, 파랑색으로 표시한 화살표들이다.

파랑색 화살표들을 보게되면, 토네이도가 2칸씩 움직인다는 것을 알 수 있다.

또한, "2칸씩 움직이는 행위를 총 2번한다." 라는 것을 알 수 있다.

이어서, 토네이도가 3칸씩 움직이는 경우를 한번 보자.

.

위의 그림에서 주황색으로 색칠한 화살표들이 토네이도가 3칸씩 움직이는 경우이다.

보면, 3칸씩 움직이는 행위를 총 2번한다는 것을 알 수 있다.

그럼 여기서 우리가 지금까지 알아본 토네이도의 움직임을 통해서 특징을 한번 적어보자.

1. 토네이도의 움직이는 계속해서 증가한다. [ 빨강색 화살표 = 1칸 , 파랑색 화살표 = 2칸 , 주황색 화살표 = 3칸 ]

2. 토네이도는 각 칸수만큼 움직이는 행위를 반드시 '2번' 진행한다.

2번에 대해서 조금 더 구체적으로 설명해보자면, 위의 그림에서 빨강색 화살표도 2개, 파랑색 화살표도 2개, 주황색 화살표도 2개라는 것을 확인할 수 있다.

화살표의 색깔을 나눈 기준은 ? 바로 "토네이도가 움직이는 칸 수" 이다.

빨강색 화살표는 토네이도가 1칸만 움직일 때를 표시한 것이고

파랑색 화살표는 토네이도가 2칸만 움직일 때를 표시한 것이고

주황색 화살표는 토네이도가 3칸만 움직일 때를 표시한 것이다.

즉, 토네이도는 계속해서 움직이는 칸수가 증가하게 되는데, 몇 칸을 움직이던 간에, 해당 칸 수 만큼 움직이는 행위를 2번 반복한다는 것을 알 수 있다.

그 이후의 토네이도의 움직임에 대해서도 눈으로만 한번 해보면, 4칸 움직이는 것도, 5칸 움직이는 것도 6칸 움직이는 것도... 모두 공통되게 2번씩만 움직인 다는 것을 알 수 있다.

#1 - 2) 토네이도의 진행 방향

그럼 이번에는 토네이도의 진행방향에 대해서 이야기를 한번 해보자.

진행방향이 정말 제멋대로 바뀌는 것 같지만, 일관된 규칙을 가지고 변하고 있다.

지금부터, 진행방향을 [ 동 서 남 북 ] 으로 표시해보자.

.

위의 맵에 본인이 화살표마다 색깔을 한번 넣어봤다.

파랑색 화살표 = 동쪽방향 , 빨강색 화살표 = 서쪽방향 , 주황색 화살표 = 남쪽방향 , 초록색 화살표 = 북쪽방향

을 의미하는 것이다.

토네이도의 가장 첫 움직임부터 진행방향을 순차적으로 적어보면...

서 - 남 - 동 - 북 - 서 - 남 - 동 - 북 - 서 - 남 - 동 - 북 ....

이런식으로 진행된다는 것을 알 수 있다. 즉 ! 토네이도는 서 - 남 - 동 - 북 의 움직임을 반복해서 진행하고 있다는 것을 알 수 있다.

그럼 ! 더 나아가서 언제 진행방향이 바뀌는지 알아보자.

진행방향은 "현재 움직여야 하는 칸 수를 모두 다 움직이는 타이밍" & "2번 반복을 끝낸 타이밍" 에 변하게 된다.

가장 처음 토네이도가 움직이는 상황을 보자.

가장 처음 토네이도가 움직여야 하는 칸 수는 "서쪽으로 한 칸" 움직여야 한다.

그럼, "한 칸 움직이고 나서 진행방향의 변화"가 일어나게 된다. 하지만 아직 "한 칸 움직이는 행위를 한번 더" 해줘야 한다.

왜 ?? 우리가 위에서 이야기했듯이, 토네이도는 "움직여야 하는 칸 수만큼 움직이는 행위를 2번 반복" 해야 하기 때문이다.

즉, "서쪽으로 한 칸" 움직인 후, 진행방향이 바뀐 후, "남쪽으로 한 칸" 움직이게 될 것이다.

그리고 이 후, 동쪽으로 진행방향이 바뀌게 된다.

방금 위의 상황에서 진행방향이 바뀌게 된 타이밍을 적어보면 다음과 같다.

1. 서쪽으로 한 칸 움직여야 하는 상황에서, 서쪽으로 한 칸 움직인 후 진행방향이 바뀌었다.

   = 현재 토네이도가 움직여야 하는 칸 수를 모두 다 움직이는 타이밍에 진행방향이 바뀌었다.

2. 한 칸 움직이는 행위를 한번 더 하기 위해서, 남쪽으로 한 칸 움직인 후 진행방향이 바뀌었다.

   = 토네이도가 움직이는 칸수에 대한 행위를 2번 반복을 끝낸 타이밍에 진행방향이 바뀌었다.

토네이도는 위와 같은 움직임의 특징을 가지고 있다. 정리해보고 조금만 더 이야기를 해보자.

1. 토네이도는 처음에는 1칸 움직이는 것으로 시작해서, 점차 2칸, 3칸, .. 증가하는 형태로 움직인다.

2. 토네이도는 움직여야 하는 칸 수를 반드시 2번 반복하게 된다.

3. 토네이도의 진행방향은, "움직여야 하는 칸 수를 다 움직인 후에" 변하게 되고, "2번 반복을 끝낸 타이밍" 에

   변하게 된다.

#1 - 3) 토네이도가 소멸되는 시점

그럼, 과연 토네이도가 저 움직임을 언제까지 하게 될까 ??

.

위의 맵에서 토네이도가 빨강색 화살표를 진행하고 난 후에는 소멸되게 될 것이다.

그런데 여기서 우리가 지금까지 했던 이야기에 위배되는 상황이 하나 발생하게 된다.

빨강색 화살표는 몇 칸을 움직이는 경우일까?? 직접 세보면, 6칸을 움직인다는 것을 알 수 있다.

우리는 이전에, 각 칸수만큼 움직이는 행위를 "반.드.시 2번만" 반복 한다는 것을 알고 있다.

그런데 위의 맵에서 6칸을 움직이는 행위를 빨강색 화살표로 칠해보면 다음과 같다.

.

정말 이상하게도, 다른 칸 수 만큼 움직이는 것은 다 2번씩만 반복되었지만, 6칸 움직이는 것만 3번 반복되는 것을 알 수 있다.

사실은, 6칸 움직이는 것만 3번 반복되는 것이 아니다.

.

위의 그림에서 파랑색 화살표는 사실 "7칸 움직여야 하는 상황" 이라고 계산되고 움직이고 있을 것이다.

하지만 7칸을 움직이게 되면 맵 범위를 벗어나기 때문에, 위의 그림에서는 맵 범위 안에 있는 것 처럼 표시하기 위해서 표시되었을 뿐, 실제로 토네이도가 맵 범위를 벗어나도 계속해서 움직인다면 다음과 같이 표시될 것이다.

.

실제로는 이렇게 움직이고 있다는 것이다.

하지만, 저렇게 움직이면 토네이도가 소멸하게 된다.

즉 ! 토네이도의 소멸 타이밍은 "토네이도가 N칸을 움직여야 하는 타이밍" 이 오게되면, 소멸되어진다는 것이다.

바로 소멸이 될까?? 아니다. 위의 그림에서도 봤듯이 실제로 7칸을 움직이고 소멸되어진다.

즉 ! 토네이도가 N칸을 움직여야 하는 타이밍이 오게되면, 해당 움직이는 칸 만큼 움직인 후 소멸되어진다 라는 것을 알 수 있다.

소스코드로 보면 다음과 같다.

int x = (N + 1) / 2;
int y = (N + 1) / 2;
int Dir = 1;        
int Move_Cnt = 1;    
 
while (1)
{
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < Move_Cnt; j++)
        {
            Spread_Sand(x, y, Dir);
            x += dx[Dir];
            y += dy[Dir];
        }
        Dir = Change_Dir(Dir);
    }
 
    Move_Cnt++;
    if (Move_Cnt == N)
    {
        for (int j = 0; j < Move_Cnt; j++)
        {
            Spread_Sand(x, y, Dir);
            x += dx[Dir];
            y += dy[Dir];
        }
        break;
    }
}

line8)에서 보게되면, "움직여야 하는 칸 수를 2번씩 반복한다" 라는 것을 나타내고 있는 반복문이다.

line10)은 토네이도가 움직여야 하는 칸 수 만큼 움직이기 위한 반복문이다.

line16)은 진행방향이 바뀌는 타이밍에 진행방향을 바꿔주는 것이다.

line20)의 조건문은 토네이도가 소멸하기 전, 마지막 움직임을 가질 때 걸리는 조건문이다.

#2. 모래가 흩날리는 부분

모래가 흩날리는 비율을 동 , 서 , 남 , 북으로 움직일 때 모두 그려보면 다음과 같다.

..

위와 같은 비율로 모래가 흩날려지게 된다.(토네이도가 (x , y)에서 (xx , yy)로 진행하는 경우입니다.)

본인은 그래서 위의 흩날리는 10개의 좌표를 모두 배열에 매핑시켜주었다.

(x , y)에서 (xx , yy)로 진행한다고 가정했을 때, (x , y)를 기준으로 10개의 좌표를 배열에 매핑 시켜 준 것이다.

10개의 좌표인 이유는 모래가 흩날리는 좌표가 총 10개가 있기 때문이다.

(1 , 1 , 7 , 7 , 10 , 10 , 2 , 2 , 5 , a) 이렇게 10개가 있기 때문이다.

소스코드로 나타내면 다음과 같다.

int xdx[4][10] = { { -1, 1, -1, 1, -1, 1, -2, 2, 0, 0 },{ -1, 1, -1, 1, -1, 1, -2, 2, 0, 0 },
                  { 0, 0, 1, 1, 2, 2, 1, 1, 3, 2}, { 0, 0, -1, -1, -2, -2, -1, -1, -3, -2} };
int ydy[4][10] = { { 0, 0, 1, 1, 2, 2, 1, 1, 3, 2}, { 0, 0, -1, -1, -2, -2, -1, -1, -3, -2},
                  { -1, 1, -1, 1, -1, 1, -2, 2, 0, 0}, {-1, 1, -1, 1, -1, 1, -2, 2, 0, 0} };
int Percent[9] = { 1, 1, 7, 7, 10, 10, 2, 2, 5 };

이런 배열들을 만들어 주었다.

xdx배열과 ydy배열에서 [4]가 의미하는 곳은 '동서남북' 을 의미한다. [10]이 의미하는 곳은, 모래가 흩날릴 수 있는 총 10개의 위치를 의미한다. 그리고 순서는 Percent배열에서 나와있듯이, 1%로 흩날리는 좌표 2개, 7%만큼 흩날리는 좌표 2개, 10%만큼 흩날리는 좌표 2개, 2%만큼 흩날리는 좌표 2개, 5%만큼 흩날리는 좌표 1개 순서대로 매핑을 시켜 주었다.

본인이 설정한 좌표의 우선순위는 "위쪽에 있는 것이 우선 or 왼쪽에 있는 것이 우선" 으로 설정해 주었다.

몇 가지 예를 들어보면..

(x , y)에서 (xx , yy)로 동쪽으로 움직이는 경우를 생각해보자. 본인에게 동쪽은 '0'으로 매핑되어 있다.

.

그럼, xdx[0]과 ydy[0] 부분을 찾는 것이다. 그럼 가장 먼저, 1%로 흩날리는 좌표를 보게되면 2개의 좌표가 존재한다.

(x , y)를 기준으로 위쪽에 한개, 아래쪽에 한개. 본인에게 우선순위는 위쪽에 있는 것이 우선이다.

즉, xdx[0][0] = -1 , ydy[0][0] = 0 , xdx[0][1] = 1 , ydy[1] = 0 이 되는 것이다.

왜냐하면, 1%로 흩날리는 좌표는 2개가 존재하는데, 더 우선순위를 갖는 것은 위쪽이라고 했으니, 위쪽에 있는 좌표부터 탐색을 하는 것이다. 위쪽에 있는 좌표를 (x , y)를 통해서 나타내면 (x - 1 , y) 가 된다.

이런식으로 다 매핑을 시킨 것이다.

우리가 보통 다른 문제들에서 "현재 좌표에서 상하좌우를 탐색할 수 있다" 라고 할 때,

int dx[] = { 0, 0, 1, -1 } , int dy[] = { 1, -1, 0, 0 } 과 같이, 현재 좌표를 기준으로 탐색할 수 있는 좌표를 설정해주는 것과 동일한 것이다. 단지, 그 탐색할 수 있는 좌표가 10개가 있는 것이고, 그 10개에 대해서 매핑을 해준 것이다.

void Spread_Sand(int x, int y,int Dir)
{
    int xx = x + dx[Dir];
    int yy = y + dy[Dir];
    if (MAP[xx][yy] == 0) return;
 
    int Sand = MAP[xx][yy];
    int Temp = Sand;
    for (int i = 0; i < 9; i++)
    {
        int nx = x + xdx[Dir][i];
        int ny = y + ydy[Dir][i];
        int Per = Percent[i];
        int Plus = (Temp * Per) / 100;
 
        if (nx < 1 || ny < 1 || nx > N || ny > N) Answer += Plus;
        else MAP[nx][ny] += Plus;
        
        Sand -= Plus;
    }
    int nx = x + xdx[Dir][9];
    int ny = y + ydy[Dir][9];
 
    if (nx < 1 || ny < 1 || nx > N || ny > N) Answer += Sand;
    else MAP[nx][ny] += Sand;
    MAP[xx][yy] = 0;
}

본인이 구현한 코드이다. 위의 매핑된 배열을 통해서 구현한 것이다.

line9)에서 보게되면 10개가 아닌 9개의 좌표에 대해서만 탐색을 한다. 왜냐하면, 마지막 10번째 좌표는 a로써, 남은 모래가 모두 움직이는 곳이기 때문에 따로 몇 %만큼 추가되는 좌표가 아니기 때문에 계산을 할 수가 없다.

대신 line 21 ~) 이후에 보면 'a'좌표에 대해서는 따로 계산을 해주는 것을 알 수 있다.

그럼 모래가 격자밖으로 나간 양은 어떻게 구할까 ?? 모래를 흩날리는 과정에서, 맵의 범위 내에 있는 좌표가 아니라면 그 모래들은 격자밖으로 나간 양이 된다. 즉, line16)과 line24)에서 격자밖으로 나간 모래의 양이 계산되는 것을 알 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define MAX 510
#define endl "\n"
using namespace std;
 
int N, Answer;
int MAP[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
// 1 1 7 7 10 10 2 2 5 순서
int xdx[4][10] = { { -1, 1, -1, 1, -1, 1, -2, 2, 0, 0 },{ -1, 1, -1, 1, -1, 1, -2, 2, 0, 0 },
                  { 0, 0, 1, 1, 2, 2, 1, 1, 3, 2}, { 0, 0, -1, -1, -2, -2, -1, -1, -3, -2} };
int ydy[4][10] = { { 0, 0, 1, 1, 2, 2, 1, 1, 3, 2}, { 0, 0, -1, -1, -2, -2, -1, -1, -3, -2},
                  { -1, 1, -1, 1, -1, 1, -2, 2, 0, 0}, {-1, 1, -1, 1, -1, 1, -2, 2, 0, 0} };
int Percent[9] = { 1, 1, 7, 7, 10, 10, 2, 2, 5 };
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) 
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
int Change_Dir(int Dir)
{
    if (Dir == 0) return 3;
    if (Dir == 1) return 2;
    if (Dir == 2) return 0;
    if (Dir == 3) return 1;
}
 
void Spread_Sand(int x, int y,int Dir)
{
    int xx = x + dx[Dir];
    int yy = y + dy[Dir];
    if (MAP[xx][yy] == 0) return;
 
    int Sand = MAP[xx][yy];
    int Temp = Sand;
    for (int i = 0; i < 9; i++)
    {
        int nx = x + xdx[Dir][i];
        int ny = y + ydy[Dir][i];
        int Per = Percent[i];
        int Plus = (Temp * Per) / 100;
 
        if (nx < 1 || ny < 1 || nx > N || ny > N) Answer += Plus;
        else MAP[nx][ny] += Plus;
        
        Sand -= Plus;
    }
    int nx = x + xdx[Dir][9];
    int ny = y + ydy[Dir][9];
 
    if (nx < 1 || ny < 1 || nx > N || ny > N) Answer += Sand;
    else MAP[nx][ny] += Sand;
    MAP[xx][yy] = 0;
}
 
void Solution()
{
    int x = (N + 1) / 2;
    int y = (N + 1) / 2;
    int Dir = 1;        
    int Move_Cnt = 1;    
 
    while (1)
    {
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < Move_Cnt; j++)
            {
                Spread_Sand(x, y, Dir);
                x += dx[Dir];
                y += dy[Dir];
            }
            Dir = Change_Dir(Dir);
        }
 
        Move_Cnt++;
        if (Move_Cnt == N)
        {
            for (int j = 0; j < Move_Cnt; j++)
            {
                Spread_Sand(x, y, Dir);
                x += dx[Dir];
                y += dy[Dir];
            }
            break;
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}