[백준 Baekjoon] 20056번 마법사 상어와 파이어볼 - JAVA

[백준 Baekjoon] 20056번 마법사 상어와 파이어볼 - JAVA

---

문제 풀이

List<FireBall> list : 파이어볼을 저장할 리스트입니다.

Queue<FireBall>[][] grid : 이동이 끝난 파이어볼이 저장될 큐 2차원 배열입니다.

 

M번 파이어볼의 정보를 입력받아 리스트에 추가합니다.

파이어볼은 위치 (r, c), 질량 m, 방향 d, 속력 s 순서이지만, 입력은 위치 (r, c), 질량 m, 속력 s, 방향 d 로 속력과 방향이 반대입니다.

 

 

1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.

리스트에 존재하는 모든 파이어볼의 x, y값을 변경해줍니다.

// 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
f.r = (N + f.r + dx[f.d] * (f.s % N)) % N;
f.c = (N + f.c + dy[f.d] * (f.s % N)) % N;

N번 이상 이동할 경우 N으로 나머지 연산한 결과와 동일함으로 (f.s % N)을 해줍니다.

dx[f.d]는 방향으로 si(f.s % N)만큼 dx[f.d] * (f.s % N)을 통해 이동해줍니다.

행과 열의 0번째 칸이 N-1번째 칸과 이어져있기 때문에 격자를 벗어나는 경우를 처리해주어야 합니다.

N + f.x + dx[f.d] * (f.s % N)) % N 에서 앞에 N을 더해주고 마지막에 N으로 나머지 연산하여 이어져있도록 하였습니다.

 

여러 개의 파이어볼이 있을 수 있어 격자를 큐로 만들고 추가하는 방식으로 하였습니다.

// 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
grid[f.r][f.c].add(f);

 

2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.

격자의 칸에 사이즈가 2 이상인 경우 합쳐집니다.

if (grid[i][j].size() >= 2)

격자에 존재하는 모든 파이어올의 질량, 속력의 합을 구하고, 모두 홀수인지, 짝수인지 검사합니다.

int m_sum = 0, s_sum = 0;
int cnt_sum = grid[i][j].size(); // 합쳐진 파이어볼의 개수
boolean odd = true, even = true;

// 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
while (!grid[i][j].isEmpty()) {
    FireBall f = grid[i][j].poll();

    m_sum += f.m; // 합쳐진 파이어볼 질량의 합
    s_sum += f.s; // 합쳐진 파이어볼 속력의 합

    // 파이어볼의 방향이 모두 홀수이거나 모두 짝수인지
    if (f.d % 2 == 0) {
        odd = false;
    } else {
        even = false;
    }

    list.remove(f);
}

같은 칸의 파이어볼은 모두 합쳐짐으로 리스트에서 삭제해줍니다.

 

질량과 속력을 5로 나누고, 질량이 0인지 검사하여 0인 경우 소멸됩니다.

// 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
int nm = m_sum / 5;

// 질량이 0인 파이어볼은 소멸되어 없어진다.
if (nm == 0) {
    continue;
}

// 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋
int ns = s_sum / cnt_sum;

합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7으로 새로운 파이어볼 4개를 추가해줍니다.

if (odd | even) { // 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면
    for (int k = 0; k < 8; k += 2) { // 방향은 0, 2, 4, 6
        list.add(new FireBall(i, j, nm, k, ns));
    }
} else { // 그렇지 않으면
    for (int k = 1; k < 8; k += 2) { // 1, 3, 5, 7
        list.add(new FireBall(i, j, nm, k, ns));
    }
}

만약 같은 칸에 2개 이상 존재하지 않는다면 격자 칸에서 제거해줍니다. 해당 파이어볼은 리스트에 남아있으므로 문제없습니다.

else {
    grid[i][j].clear();
}

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N;

    public static List<FireBall> list;
    public static Queue<FireBall>[][] grid;

    public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    public 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());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();

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

            list.add(new FireBall(r, c, m, d, s));
        }

        grid = new Queue[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = new LinkedList<>();
            }
        }

        while (K-- > 0) {
            move();

            combineAndDivide();
        }

        int answer = 0;
        for (FireBall f : list) {
            answer += f.m;
        }

        System.out.println(answer);
    }

    public static void move() {
        for (FireBall f : list) {
            // 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
            f.r = (N + f.r + dx[f.d] * (f.s % N)) % N;
            f.c = (N + f.c + dy[f.d] * (f.s % N)) % N;

            // 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
            grid[f.r][f.c].add(f);
        }
    }

    public static void combineAndDivide() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 2개 이상의 파이어볼이 있는 칸
                if (grid[i][j].size() >= 2) {
                    int m_sum = 0, s_sum = 0;
                    int cnt_sum = grid[i][j].size(); // 합쳐진 파이어볼의 개수
                    boolean odd = true, even = true;

                    // 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
                    while (!grid[i][j].isEmpty()) {
                        FireBall f = grid[i][j].poll();

                        m_sum += f.m; // 합쳐진 파이어볼 질량의 합
                        s_sum += f.s; // 합쳐진 파이어볼 속력의 합

                        // 파이어볼의 방향이 모두 홀수이거나 모두 짝수인지
                        if (f.d % 2 == 0) {
                            odd = false;
                        } else {
                            even = false;
                        }

                        list.remove(f);
                    }

                    // 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
                    int nm = m_sum / 5;

                    // 질량이 0인 파이어볼은 소멸되어 없어진다.
                    if (nm == 0) {
                        continue;
                    }

                    // 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋
                    int ns = s_sum / cnt_sum;

                    if (odd | even) { // 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면
                        for (int k = 0; k < 8; k += 2) { // 방향은 0, 2, 4, 6
                            list.add(new FireBall(i, j, nm, k, ns));
                        }
                    } else { // 그렇지 않으면
                        for (int k = 1; k < 8; k += 2) { // 1, 3, 5, 7
                            list.add(new FireBall(i, j, nm, k, ns));
                        }
                    }
                } else {
                    grid[i][j].clear();
                }
            }
        }
    }

    public static class FireBall {
        int r, c, m, d, s;

        public FireBall(int r, int c, int m, int d, int s) {
            this.r = r;
            this.c = c;
            this.m = m;
            this.d = d;
            this.s = s;
        }
    }
}