[백준]20056번. 마법사 상어와 파이어볼

[문제]

 

www.acmicpc.net/problem/20056

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

 

[풀이]

 

구현 문제로 k번의 이동 후 , 남아있는 파이어볼의 질량을 구하는 문제이다.

 

파이어볼이 이동하고 , 파이어볼이 2개 이상 존재하는 곳은 파이어볼이 하나로 합쳐진 뒤 4개로 나누어진다.

따라서 파이어볼이 이동하는 move 함수와, 파이어볼이 나누어지는 solve 함수를 따로 구현하였다.

 

먼저 입력받은 파이어볼의 정보를 fire라는 구조체 벡터에 저장한다.

 

move 함수에서는 fire 구조체 벡터에 저장된 파이어볼이 하나씩 움직인다.

이 때 신경써야 할 부분은 '1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.'

따라서 속력 s를 N으로 나머지 연산을 하고, 0보다 작거나 N보다 크고 같은 경우 N을 더해주거나 빼줬다.

한 공간에 2개 이상의 파이어볼이 존재한다면 나누어줘야 하므로 이차원 배열 벡터를 사용해 파이어볼의 위치를 저장했다.

 

solve 함수에서는 파이어볼이 움직이는 함수로 map의 사이즈가 2보다 크거나 같은 경우 나누어지도록 하였다.

여기서 조심해야 될 부분은 해당 좌표에 존재하는 파이어볼의 방향이 모두 짝수이거나 홀수인 경우와 그렇지 않을 경우의 방향이 달라지므로 신경써줘야 된다.

파이어볼을 나누고 파이어볼의 좌표도 달라졌으므로 map도 clear 해줘야된다. 

또한 파이어볼의 좌표, 속력, 방향, 무게가 모두 바꼈으므로 fire 구조체도 update 해줘야된다.

 

이와 같은 방법으로 K번 반복한 뒤 , 존재하는 파이어볼의 무게를 모두 더하여 출력하면 된다. 

 

[코드]

 

시간 : 16ms

 

#include <iostream>
#include <vector>

#define MAX 51

using namespace std;

struct FIRE{
    int x,y;
    int m,s,d;
};

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

int N,M,K;
vector <int> map[MAX][MAX];
vector <FIRE> fire;

void solve()
{
    vector <FIRE> tmp;

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int num = map[i][j].size();

            if(num >= 2){
                int m=0,s=0,d=0;
                bool odd = false;
                bool even = false;
                for(int k=0;k<num;k++){
                    int idx = map[i][j][k];
                    m += fire[idx].m;
                    s += fire[idx].s;
                    if(fire[idx].d%2 == 0)  even=true;
                    else    odd= true;
                }
                m = m/5;
                s = s/num;
                
                if(m!=0){
                    if(odd && even)  d=1;
                    else    d=0;
                    
                    for(int k=0;k<4;k++){
                        tmp.push_back({i,j,m,s,d});
                        d+=2;
                    }
                }
            }
            else if(num==1)    {
                int idx = map[i][j][0];
                tmp.push_back(fire[idx]);
            }
            map[i][j].clear();
        }
    }
    fire.clear();
    fire = tmp;
}

void move()
{
    for(int i=0;i<fire.size();i++){
                
        int x= fire[i].x;
        int y= fire[i].y;
        int s= fire[i].s;
        int d= fire[i].d;
        
        s = s%N;
        x = x+dx[d]*s;
        y = y+dy[d]*s;
        
        if(x < 0)   x+=N;
        if(x >= N) x -=N;
        
        if(y < 0)   y+=N;
        if(y >= N) y-= N;
        
        fire[i].x = x;
        fire[i].y = y;
        map[x][y].push_back(i);
    }
}

int main(void)
{
    cin >> N >> M >> K;
    
    for(int i=0;i<M;i++){
        int x,y,m,s,d;
        cin >> x >> y >> m >> s >> d;
        fire.push_back({x,y,m,s,d});
    }
    
    for(int i=0;i<K;i++){
        move();
        solve();
    }
    
    int ans=0;
    for(int i=0;i<fire.size();i++)  ans += fire[i].m;
    
    cout << ans;
    return 0;
}