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

🔗 문제

20056번: 마법사 상어와 파이어볼

20056번: 마법사 상어와 파이어볼

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.

 

=> 격자의 범위가 벗어나는 법은 없다. 5칸 짜리에서 8번칸 이동해야하면 3칸에 위치시키면 된다. 

==> x%=N

 

 

🖍 풀이

 

간단하게 정리하면 이렇게 풀 수있다. 

while(K--)
{
	// 1. 파이어볼의 동시 이동
	// 2. 파이어볼 나누기
}

 

 

1. 파이어볼의 동시 이동

• 파이어볼이 가져야할 정보
  • 위치 (r, c)
  • 질량 m
  • 속력 s
  • 방향 d

struct info
{
    info() = default;
    info(int r, int c, int m, int s, int d)
    :r(r), c(c), m(m), s(s), d(d){}
    
    int r, c, m, s, d;
};

 

 

✔️파이어볼은 같은 칸에 여러 파이어볼이 있을 수 있다.

자료구조를 어떻게 가져야할지 고민이 많았는데 map을 다 돌면서 파이어볼을 찾는게 비효율적이라고 생각해서 파이어볼을 옮길 때는 fireball에 담긴 것만 돌려주었다. 그러면서 map에 몇개의 파이어볼이 있는지 알아야하니까 map.push_back으로 같은 칸의 파이어볼 개수를 카운팅해준다.

std::vector<info> map[MAX][MAX];
std::queue<info> fireball;

 

✔️파이어볼은 현재 위치 (r, c)에서 s*d 만큼 이동한다.

 

[TIP] outofBound 나오는 사람 주목

r + speed * dx[d] 이렇게 연산하시나요? (경험담) 
이 친구는 1 + 10*-1 = -49가 될 수 있겠죠? :-)

 

 

2. 파이어볼 나누기

• 같은 칸에 2개 이상의 파이어볼이 있다면 걔네들의 질량과 속력의 합을 구한다.
  • (정수) 질량의 합 / 5  
    • 질량이 0이면 파이어볼은 소멸한다. 
  • (정수) 속력의 합 / 파이어볼 개수
  • 방향을 아래처럼 4개로 나눈다. (위치가 아니라 방향이다)
    • 모두 짝수 or 홀수0, 2, 4, 6
    • 아니라면 1, 3, 5, 7

map을 돌면서 map.size()==1이라면 fireball에 넣어주고 넘긴다. 2개 이상이라면 위 논리대로 코드를 짜준다.

겸사 겸사 할일이 끝나면 map.clear()로 맵 크기를 초기화해주는 것도 잊지 않기!!

 

💾  소스

#include <iostream>
#include <queue>
#include <vector>

const int MAX  = 50 + 1;
const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int N, M, K;

struct info
{
    info() = default;
    info(int r, int c, int m, int s, int d)
    :r(r), c(c), m(m), s(s), d(d){}
    
    int r, c, m, s, d;
};
std::vector<info> map[MAX][MAX];
std::queue<info> fireball;

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=N)
        return false;
    return true;
}

void move()
{
    while(!fireball.empty())
    {
        auto e = fireball.front();
        fireball.pop();
        
        e.r = e.r + (e.s * dx[e.d]);
        e.c = e.c + (e.s * dy[e.d]);

        while(e.r < 0) e.r += N;
        if(e.r >= N) e.r %= N;
        
        while(e.c < 0) e.c += N;
        if(e.c >=N) e.c %= N;

        map[e.r][e.c].push_back(e);
    }
}

void division()
{
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
        {
            if(map[i][j].size() == 1)
            {
                fireball.push(map[i][j][0]);
            }
            else if(map[i][j].size() > 1)
            {
                int massive = 0, speed = 0;
                bool even = false, odd = false;
                
                for(int k=0; k<map[i][j].size(); ++k)
                {
                    massive += map[i][j][k].m;
                    speed += map[i][j][k].s;
                    
                    if(map[i][j][k].d % 2 == 0) even = true;
                    else odd = true;
                }

                massive = massive/5;
                if(massive > 0)
                {
                    speed = speed/map[i][j].size();
                    for(int d = (even != odd ? 0 : 1); d<8; d+=2)
                    {
                        fireball.push({i, j, massive, speed, d});
                    }
                }
            }
            
            // 초기화
            map[i][j].clear();
        }
    }
}

int solve()
{
    int answer = 0;
    
    while(K--)
    {
        move();
        division();
    }
    
    while(!fireball.empty())
    {
        answer += fireball.front().m;
        fireball.pop();
    }

    return answer;
}

int main()
{
    int r, c, m, d, s;
    std::cin >> N >> M >> K;
    
    for(int i=0; i<M; ++i)
    {
        std::cin >> r >> c >> m >> s >> d;
        fireball.push({r-1, c-1, m, s, d});
    }

    std::cout << solve();
    
    return 0;
}