이번에 풀어본 문제는
백준 20056번 마법사 상어와 파이어볼 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Fireball
{
    int x,y;
    int cnt,mass,speed,dir;
    boolean sameDir = true;

    public Fireball(int x, int y, int cnt, int mass, int speed, int dir)
    {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        this.mass = mass;
        this.speed = speed;
        this.dir = dir;
    }
}
public class Main {
    static int result;
    static int N,M,K;
    static Fireball [][] map;
    static Queue<Fireball> q;
    static Queue<Fireball> tmp_q;
    static int [] dx = {-1,-1,0,1,1,1,0,-1};
    static int [] dy = {0,1,1,1,0,-1,-1,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        q = new LinkedList<>();
        tmp_q = new LinkedList<>();
        for(int i = 0; i < M; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            q.add(new Fireball(r,c,1,m,s,d));
        }

        while(K-- > 0)
        {
            tmp_q = new LinkedList<>();
            while(!q.isEmpty())
            {
                Fireball cur = q.poll();

                int mx = cur.x + (dx[cur.dir] * cur.speed);
                int my = cur.y + (dy[cur.dir] * cur.speed);

                while(!isValid(mx)) mx = move(mx);
                while(!isValid(my)) my = move(my);

                tmp_q.add(new Fireball(mx,my,1,cur.mass,cur.speed,cur.dir));
            }
            setFire();
            separateFire();
        }
        for(Fireball f : q)
        {
            result += f.mass;
        }
        System.out.print(result);
    }
    static void setFire()
    {
        map = new Fireball[N+1][N+1];
        while(!tmp_q.isEmpty())
        {
            Fireball cur = tmp_q.poll();

            if(map[cur.x][cur.y] != null)
            {
                combFire(map[cur.x][cur.y],cur);
            }
            else map[cur.x][cur.y] = cur;
        }
    }
    static void separateFire()
    {
        for(int i = 1; i <= N; ++i)
        {
            for(int j = 1; j <= N; ++j)
            {
                if(map[i][j] != null)
                {
                    Fireball cur = map[i][j];
                    if(cur.cnt > 1)
                    {
                        int tmp_m = cur.mass / 5;
                        if(tmp_m == 0)
                        {
                            map[i][j] = null;
                            continue;
                        }
                        int tmp_s = cur.speed / cur.cnt;
                        int dir_idx = cur.sameDir ? 0 : 1;

                        for(int idx = dir_idx; idx <= 7; idx+=2)
                        {
                            q.add(new Fireball(i,j,1,tmp_m,tmp_s,idx));
                        }
                    }
                    else q.add(cur);
                }
            }
        }
    }
    static void combFire(Fireball fst, Fireball sec)
    {
        fst.cnt++;
        fst.mass += sec.mass;
        fst.speed += sec.speed;

        if(fst.sameDir)
        {
            int tmp_dir = fst.dir + sec.dir;
            if(tmp_dir % 2 > 0) fst.sameDir = false;
        }
    }
    static boolean isValid(int p)
    {
        return p > 0 && p <= N;
    }
    static int move(int p)
    {
        if(p <= 0) return p + N;
        else if(p > N) return p - N;
        else return p;
    }
}

📝 풀이

1회 반복시,
맵에있는 파이어볼을 각각의 방향과 속도에 맞게 이동시킵니다.
파이어볼은 각자의 질량을 지니고 있는데, 만약 같은 좌표에 파이어볼이 겹칠경우 질량과 속도를 합쳐줍니다.
모든 이동이 끝난 후, 한 좌표에 두 개 이상의 파이어볼이 존재한다면 주어진 조건에 맞게 질량과 속도, 방향을 분배해주고 4개의 파이어볼로 분리시켜줍니다. 위와 같은 반복을 K번 수행했을 때, 남은 파이어볼들의 질량의 합을 출력해주는 문제입니다.

먼저 q에 파이어볼들의 정보를 담아 순차적으로 이동시킵니다. tmp_q에서는 이동된 좌표를 지닌 파이어볼들이 존재합니다. 모든 파이어볼들을 이동시켰다면, setFire 함수에서 map에다가 이동된 좌표의 정보를 담아줍니다. 이 때, 이미 맵에 값이 들어있다면 불이 겹쳐지는 경우이므로 값을 누적해서 더해줍니다. 모든 이동에 대한 계산이 끝났다면, separateFire 내에서 카운트값을 체크하여 카운트가 2 이상인 불들은 4개로 분리하여 다음 사용할 q에 담고, 이외의 값은 그대로 q에 담아줍니다.
K번 수행이 완료된 후, q에 남은 값을 탐색하며 result에 질량값을 누적해주면 해결됩니다.

📜 후기

한 가지 조건을 잘못 이해해서 조금 시간이 걸렸습니다.
불의 이동이 끝나고 2번 조건을 수행할 때, 바로 4방향으로 불을 퍼뜨리는것이 아니라, 조건에 맞게 방향을 부여하여 불을 4개로 분리만 시켜두고(같은 좌표에), 다음 반복을 수행할 때 1번과 동일하게 이동을 수행합니다.
문제를 이해할 때 조금 헷갈릴만한 조건인 것 같아 참고하시라고 적어봅니다!
화이팅~