[ 백준 20056 ] 마법사 상어와 파이어볼 (C++)

백준의 마법사 상어와 파이어볼(20056) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

상어가 K 이동을 명령한 후, 남아있는 파이어볼들의 질량의 합을 구해야 하는 문제이다.

먼저, 주어진 맵 그리고 변수들을 어떻게 선언하고 어떻게 활용하지에 대해서 알아보고 본격적인 문제 풀이까지 진행해보자.

#1. 파이어볼

이 문제에서 가장 핵심이 되는 요소이다. 하나의 파이어볼은 다음과 같이 5가지 정보를 가지고 있다.

1. x좌표

2. y좌표

3. 질량

4. 속도

5. 방향

위와 같이 5가지 정보들을 가지고 있다.

따라서 본인은 이 5가지 정보를 하나의 자료형으로 관리하기 위해서 다음과 같은 구조체를 선언해서 사용해 주었다.

struct FIREBALL
{
    int x;
    int y;
    int Massive;
    int Speed;
    int Dir;
};

또한, 위의 구조체를 자료형으로 가지고 있는 vector를 하나 선언해서, 파이어볼들을 관리해 주었다.

#2. 맵

두 번째로 맵을 어떻게 선언하고 관리할지에 대해서 알아보자.

먼저, 맵에는 하나의 좌표에 2개 이상의 값이 들어갈 수 있다.

파이어볼이 이동하는 과정에서 2개 이상의 파이어볼이 같은 칸에 존재할 수 있기 때문이다.

따라서, "한 칸에 여러개의 값을 가질 수 있도록" 맵을 Vector로 선언해 주었다.

그리고 그 자료형은 #1에서 선언해 놓은 FIREBALL 구조체로 만들어 주었다.

왜냐하면, "맵에는 한 칸에 여러개의 값을 가질 수 있기 때문이고, 그 여러개의 값이 가지는 정보가 결국에는 #1에서 선언해놓은 파이어볼에 관한 정보들이기 때문"이다.

따라서, 본인은 맵을 vector<FIREBALL> MAP[MAX][MAX]; 이런식으로 선언해 주었다.

지금까지 선언한 자료형 및 데이터들을 정리해보면 다음과 같다.

1. 파이어볼은 [ x좌표 , y좌표 , 질량 , 속도 , 방향 ] 5개의 정보를 가질 수 있다.

   이를 관리해주기 위해서 struct FIREBALL 을 만들어 주었다.

2. 파이어볼은 여러개가 존재할 수 있고, 그 파이어볼들을 관리하기 위해서 vector<FIREBALL> 을 선언해 주었다.

3. 맵에는 한 칸에 여러개의 데이터가 동시에 들어갈 수 있고, 그 데이터는 파이어볼에 관한 데이터들이기 때문에

   맵을 vector<FIREBALL> MAP[MAX][MAX] 이라는, 구조체를 자료형으로 갖는 벡터 배열 형식으로 선언해

   주었다.

그럼 여기까지 진행했을 때, 입력을 받은 상태라고 생각해보자.

과연 입력된 값을 어디에 어떻게 저장해 주면 될까 ??

입력값으로는 초기 파이어볼의 갯수와, 각각의 파이어볼에 대한 정보를 입력으로 준다.

즉, 각각의 파이어볼에 대한 정보가 들어오면, 우리는 이정보들을 파이어볼을 관리하기 위한 vector에 삽입을 해주면 되고,

이 정보에서 얻을 수 있는 (x , y) 좌표를 가지고, MAP에서 해당 좌표에 이 파이어볼에 대한 정보를 삽입해 주면 된다.

#3. 파이어볼 움직이기

문제에서 1행은 N행과 1열은 N열과 연결되어 있다고 했으므로, 파이어볼을 각각 움직일 때 맵의 범위를 넘어갈 때, 단순히 한칸 한칸씩 움직여 줘도 충분히 움직일 수 있을 것이다.

그런데 본인은 이 움직임에 대한 횟수를 조금 줄이는 방식으로 구현하였다.

.

위와 같이 파이어볼이 위치해 있다고 가정해보자. (파이어볼이 있는 칸은 1번칸 입니다.)

위의 상황을, 맵은 3 x 3 (N = 3) 크기를 가지고 있고, 파이어볼은 '오른쪽의 방향으로 속력 5를 가지고 있는 상황' 이라고 가정해보자.

즉, 위의 그림에서 파이어볼이 오른쪽으로 5칸을 움직이게 되면 어디에 위치하게 될까 ??

아마, 2 - 3 - 1 - 2 - 3 으로 움직여서 최종적으로 3번칸에 위치하게 될 것이다.

그런데, 여기서 이렇게 5번을 직접 움직여볼 필요가 있을까 ?? 그럴 필요가 없다.

그럼, 파이어볼이 몇 칸을 움직이면 원래 자기 자리로 돌아오게 될까 ?? 바로 3칸이다. 3칸을 움직이게 된다면, 현재 파이어볼이 있는 위치로 돌아오게 될 것이다.

즉, 5칸을 움직인다 라는 것을 3칸을 움직여서 자기 자리로 온 후, 2칸을 더 움직이는 것이라고 생각할 수 있다.

그러면, 여기서 "3칸을 움직여서 자기 자리로 오는 것" 에 대해서 계산이 필요할까?? 필요하지 않다.

어쨌거나 결과적으로 본다면 자기자리로 돌아오는 것이기 때문이다.

그럼 상황을 바꿔서 위의 파이어볼의 속력이 10이라고 가정해보자. 어디에 위치하게 될까 ??

2번칸에 위치하게 될 것이다. 그럼 이를 한번 구해보자.

맵은 N x N 형태로 주어진다. 이것이 의미하는 것은 "N번 움직이게 되면, 다시 본인의 자리로 돌아옵니다" 라는 것을 의미한다.

실제로 위의 맵을 보면 3x3 크기의 맵이고, 파이어볼이 '3번' 움직이게 되면, 다시 본인의 자리로 돌아오게 된다.

그럼 이 상황에서 5번을 움직여야 한다면, 우리는 파이어볼을 몇 번만 움직여 보면 될까 ??

바로 '2번'이다. 그 값이 어떻게 나오는 걸까 ? 바로 "속력 % N" 이 된다.

"속력 % N"이라는 값이 가지는 의미는 다음과 같이 해석할 수 있다. "현재 속력으로 움직이게 되면, 속력 / N번 만큼 자기 자리에 위치하게 될 것이고, 속력 % N번칸 만큼 더 움직이면 됩니다".

위의 상황에 대입해보자.

5번을 움직여야 한다(= 속력이 5이다)면, 5 % 3 = 2. 실제로는 2칸만 움직이는 것과 같은 위치에 있게 되는 것이다.

10번을 움직여야 한다(= 속력이 10이다)면, 10 % 3 = 1. 실제로는 1칸만 움직이는 것과 같은 위치에 있게 되는 것이다.

즉, 주어진 속력만큼 한칸한칸 움직여볼 필요가 없다.

속력 % N 칸만큼만 움직여 주더라도, 최종적인 위치는 똑같을 것이다. 어느 방향을 기준으로 삼던, 똑같이 적용된다.

그런데 ! 이렇게 계산을 하더라도 맵의 범위를 넘어가는 경우가 존재한다.

.

이 경우를 한번 구해보자. 위의 파이어볼이 오른쪽으로 속력5를 가지고 있다. 어디에 위치하게 될까 ??

위에서 했던 이야기 대로라면, 5 % 3 = 2. 이 파이어볼이 위치하는 곳은, 현재 위치에서 2칸만 더 움직이면 되는 곳이다 라는 것을 알 수 있다.

그런데 저 상태에서 오른쪽으로 2칸을 더 가버리면, 맵의 범위를 벗어나게 된다.

실제로는 2칸을 더 가게 되면 '1번칸'에 위치해야 한다.

이 경우에는 N만큼을 빼주면 된다. 위의 파이어볼이 오른쪽으로 2칸을 더 가면, 4번칸에 위치하게 될 것이다.

이 때의 실제 위치를 구하기 위해서는 4번칸 - N(= 3)을 해주면 1번칸이 된다는 것을 알 수 있다.

반대의 경우도 마찬가지이다. 위의 파이어볼이 왼쪽으로 속력5를 가지고 있다. 어디에 위치하게 될까 ??

5 % 3 = 2. 왼쪽으로 2칸만 더 움직이면 되겠다 라고 해서 왼쪽으로 2칸을 더 움직이게 되면 0번칸에 위치하게 된다.

실제로는 왼쪽으로 2칸을 더 가게 되면 '3번칸'에 위치해야 한다.

이 경우에는 N만큼을 더해주면 된다. 0번칸 + N(=3)을 해주면 3번칸이 된다는 것을 알 수 있다.

이런 모듈러 연산을 통해서 파이어볼의 움직이는 횟수를 최소화 시킬 수 있다.

파이어볼 움직이기

1) "파이어볼의 속력 % N(맵의 크기)" 를 통해서 실제로 몇 칸을 움직이면 되는지 구한다.

2) 1)의 과정을 통해 움직일 칸수를 구했을 때, 맵의 범위를 넘어간다면 +N or -N을 통해서 올바른 위치를

   찾아준다.

 

최종적으로 위의 방법으로 파이어볼을 움직였다면, 도착한 좌표에 해당 파이어볼에 대한 정보를 다시 삽입해주었다.

#4. 파이어볼 나누기

#3의 과정을 진행했다면, "한 칸에 여러 개의 파이어볼이 동시에 존재하는 칸"이 있을 수도 있다.

이 경우에는 파이어볼을 나눠주어야 한다.

한 칸에 여러 개의 파이어볼이 동시에 존재한다는 것을 확인할 수 있는 것은 해당 좌표의 크기를 보면 된다.

우리는 현재 맵을 vector로 선언해 놓았고, 2개 이상의 파이어볼이 하나의 좌표에 들어가 있다면, 해당 좌표의 크기는 2 이상이 될 것이다. 우리는 해당 좌표의 크기를 통해서 파이어볼이 2개 이상 있는지 판단할 수 있다.

2개 이상의 파이어볼이 있다면, 문제에서 제시한대로 해당 파이어볼들을 나누기 위해서, 해당 파이어볼들의 질량의 합을 구해주면 되고, 속력의 합을 구해주면 된다. 동시에 파이어볼들의 방향이 홀수로만 이루어져있는지, 짝수로만 이루어져 있는지를 판단해 주었다.

위의 내용을 구현하는 것은 크게 어렵지 않지만, 그렇다면 위의 과정이 진행되고 난 후 파이어볼의 상황은 어떻게 될까??

우리는 파이어볼을 vector로 선언해서 관리해 주고 있다. 그런데, 위의 과정이 한번 진행되고 나면 어떻게 될까 ??

2개 이상의 파이어볼들이 하나로 합쳐지고, 그 파이어볼들이 다시 4개로 나눠지게 되므로 기존의 파이어볼을 관리하고 있는 vector 안에서 이를 해결하려면 굉장히 복잡한 과정이 필요하게 된다.

따라서, 본인은 이 파이어볼들에 대한 정보를 관리할 임시 vector를 하나 선언해서 처리해 주었다.

임시 vector를 하나 선언해서, 좌표의 크기가 1인 지점에 대해서는 해당 좌표에 있는 파이어볼의 정보를 삽입해 주었고,

2이상인 지점에 대해서는 4개로 나눈 후, 이 4개의 파이어볼들을 삽입해 주었다.

그리고 최종적으로는 이 임시적으로 파이어볼을 관리한 임시 vector를, 우리가 원래 관리하고 있는 vector에 복사해 주었다.

[ 소스코드 ]

#include <iostream>
#include <vector>
 
#define MAX 55
#define endl "\n"
using namespace std;
 
struct FIREBALL
{
    int x;
    int y;
    int Massive;
    int Speed;
    int Dir;
};
 
int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int T_Dir[] = { 0, 2, 4, 6 };
int F_Dir[] = { 1, 3, 5 ,7 };
 
int N, M, K;
vector<FIREBALL> MAP[MAX][MAX];
vector<FIREBALL> FireBall;
 
void Input()
{
    int Num = 0;
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++)
    {
        int r, c, m, s, d;
        cin >> r >> c >> m >> s >> d;
        FireBall.push_back({ r, c, m, s, d });
        MAP[r][c].push_back({ r, c, m, s, d });
    }
}
 
void Move_FireBall()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            MAP[i][j].clear();
        }
    }
    
    for (int i = 0; i < FireBall.size(); i++)
    {
        int x = FireBall[i].x;
        int y = FireBall[i].y;
        int Mass = FireBall[i].Massive;
        int Speed = FireBall[i].Speed;
        int Dir = FireBall[i].Dir;
 
        int Move = Speed % N;
        int nx = x + dx[Dir] * Move;
        int ny = y + dy[Dir] * Move;
        if (nx > N) nx -= N;
        if (ny > N) ny -= N;
        if (nx < 1) nx += N;
        if (ny < 1) ny += N;
        MAP[nx][ny].push_back({ nx,ny,Mass,Speed,Dir });
        FireBall[i].x = nx;
        FireBall[i].y = ny;
    }
}
 
void Sum_FireBall()
{
    vector<FIREBALL> Temp;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (MAP[i][j].size() == 0)continue;
            if (MAP[i][j].size() == 1)
            {
                Temp.push_back(MAP[i][j][0]);
                continue;
            }
            
            int Massive_Sum = 0;
            int Speed_Sum = 0;
            int Cnt = MAP[i][j].size();
 
            bool Even = true;
            bool Odd = true;
            for (int k = 0; k < MAP[i][j].size(); k++)
            {
                Massive_Sum += MAP[i][j][k].Massive;
                Speed_Sum += MAP[i][j][k].Speed;
                if (MAP[i][j][k].Dir % 2 == 0) Odd = false;
                else Even = false;
            }
            
            int Mass = Massive_Sum / 5;
            int Speed = Speed_Sum / Cnt;
            if (Mass == 0) continue;
            if (Even == true || Odd == true)
            {
                for (int k = 0; k < 4; k++)    Temp.push_back({ i, j, Mass, Speed, T_Dir[k] });
            }
            else
            {
                for (int k = 0; k < 4; k++) Temp.push_back({ i, j, Mass, Speed, F_Dir[k] });
            }
        }
    }
    FireBall = Temp;
}
 
void Solution()
{
    for (int i = 0; i < K; i++)
    {
        Move_FireBall();
        Sum_FireBall();
    }
    
    int Answer = 0;
    for(int i = 0 ; i< FireBall.size(); i++) Answer += FireBall[i].Massive;
    
    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;
}