[BOJ] 20056번 | 마법사 상어와 파이어볼 (Java)

🔗문제 보러가기

 

 

🧑🏻‍💻풀이 과정

빡구현 문제는 요구사항 별로 메서드를 잘 나눠 구현하는 게 중요하다고 생각하는데, 이렇게 해도 중간에 로직이 잘못되면 디버깅하기가 정말 어렵네요. 저는 파이어볼이 같은 위치에 있는지 파악하기 위한 2차원 Queue 배열, 현재 맵에 존재하는 파이어볼들을 관리하는 Queue 이렇게 2개를 써서 풀었습니다. 큐에서는 파이어볼 클래스 정보를 관리하구요.

class FireBall {
    FireBall(int row, int column, int mass, int velocity, int direction) {
        this.row = row;
        this.column = column;
        this.mass = mass;
        this.velocity = velocity;
        this.direction = direction;
    }

    int row, column, mass, velocity, direction;
}

 

BufferedReader를 통해 입력값을 받아주고, 2차원 큐 배열과 관리 큐를 생성해줍니다. 그리고 행, 열, 질량, 속도, 방향 정보값을 입력 받아 관리 큐에다가 넣어주었죠.

private static void initialize() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] args = br.readLine().split(" ");

    N = Integer.parseInt(args[0]);
    M = Integer.parseInt(args[1]);
    K = Integer.parseInt(args[2]);
    Field = new LinkedList[N][N];
    FireBalls = new LinkedList<>();

    // 1. 2차원 배열 각 요소마다 큐(Queue) 생성
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            Field[r][c] = new LinkedList<FireBall>();
        }
    }

    // 2. 현재 존재하는 파이어볼 정보를 담는 FireBalls 큐에 초기값 넣기
    for (int i = 0; i < M; i++) {
        args = br.readLine().split(" ");
        int row = Integer.parseInt(args[0]) - 1;
        int column = Integer.parseInt(args[1]) - 1;
        int mass = Integer.parseInt(args[2]);
        int velocity = Integer.parseInt(args[3]);
        int direction = Integer.parseInt(args[4]);

        FireBalls.add(new FireBall(row, column, mass, velocity, direction));
    }

    br.close();
}

 

입력값 받기를 완료했다면 파이어볼을 이동시키는 moveFireBalls()와 모두 이동한 파이어볼들을 처리하는 processFireBalls()를 K번 반복할 겁니다.

 

moveFireBalls()

현재 존재하는 파이어볼의 개수(FireBalls.size())만큼 for 문을 돌아 다음 위치로 이동시켜 줄 겁니다. 이때, 문제에서 주어진 맵은 무한 맵이므로 맵 밖을 넘어가도 다시 반대편으로 돌아와야 합니다. 이를 적용해주기 위해 모듈러 연산(%)을 적용했으며, 음수일 경우에는 모듈러 연산을 적용해도 그대로 음수인 경우가 있으므로 N만큼 추가로 더해주었습니다.

private static void moveFireBalls() {
    int size = FireBalls.size();

    for (int i = 0; i < size; i++) {
        FireBall fireBall = FireBalls.poll();
        int nextRow = (fireBall.row + RowDirections[fireBall.direction] * fireBall.velocity) % N;
        int nextColumn = (fireBall.column + ColumnDirections[fireBall.direction] * fireBall.velocity) % N;

        if (nextRow < 0)    nextRow += N;
        if (nextColumn < 0) nextColumn += N;

        fireBall.row = nextRow;
        fireBall.column = nextColumn;
        Field[nextRow][nextColumn].add(fireBall);
    }
}

 

processFireBalls()

전체 맵을 순회하면서 파이어볼의 개수에 따라 다른 연산을 적용합니다.

• 파이어볼의 개수가 1개인 경우 : 맵의 현재 위치에서 파이어볼을 빼내어 관리 큐(FireBalls)에 넣습니다.
• 파이어볼의 개수가 2개 이상인 경우 : 파이어볼을 하나로 합쳐 4개로 분리하는 과정 진행 → splitFireBalls()

private static void processFireBalls() {
    for (int row = 0; row < N; row++) {
        for (int column = 0; column < N; column++) {
            // 같은 곳에 파이어볼 개수가 1개인 경우 -> 관리 큐에 넣기
            if (Field[row][column].size() == 1) {
                FireBalls.add(Field[row][column].poll());
            }

            // 같은 곳에 파이어볼 개수가 2개 이상인 경우 -> 4개로 분리
            else if (Field[row][column].size() > 1) {
                splitFireBalls(row, column);
            }
        }
    }
}

 

splitFireBalls() 메서드는 같은 곳에 있는 2개 이상의 파이어볼들이 하나로 합쳐져 4개로 분리되는 요구사항을 그대로 구현한 것입니다.

private static void splitFireBalls(int row, int column) {
    int sumMass = 0, sumVelocity = 0, size = Field[row][column].size();
    boolean isAllEven = true, isAllOdd = true;

    while (!Field[row][column].isEmpty()) {
        FireBall fireBall = Field[row][column].poll();
        sumMass += fireBall.mass;
        sumVelocity += fireBall.velocity;

        if (fireBall.direction % 2 == 0)    isAllOdd = false;
        else                                isAllEven = false;
    }

    int newMass = sumMass / 5;
    int newVelocity = sumVelocity / size;

    if (newMass > 0) {
        for (int i = 0; i < 4; i++) {
            int newDirection = (isAllEven || isAllOdd) ? i * 2 : i * 2 + 1;
            FireBalls.add(new FireBall(row, column, newMass, newVelocity, newDirection));
        }
    }
}

 

이러한 과정을 K번 반복한 후, 현재 존재하는 파이어볼들의 질량 합을 출력해주면 정답입니다.

private static int getFireBallMass() {
    int result = 0;

    for (FireBall fireBall : FireBalls) {
        result += fireBall.mass;
    }

    return result;
}

 

전체 소스코드는 아래에 있습니다.

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

class FireBall {
    FireBall(int row, int column, int mass, int velocity, int direction) {
        this.row = row;
        this.column = column;
        this.mass = mass;
        this.velocity = velocity;
        this.direction = direction;
    }

    int row, column, mass, velocity, direction;
}

public class BOJ20056 {
    private static int N, M, K;
    private static int[] RowDirections = { -1, -1, 0, 1, 1, 1, 0, -1 };
    private static int[] ColumnDirections = { 0, 1, 1, 1, 0, -1, -1, -1 };
    private static Queue<FireBall>[][] Field;
    private static Queue<FireBall> FireBalls;

    public static void main(String[] args) throws Exception {
        initialize();

        for (int i = 0; i < K; i++) {
            moveFireBalls();
            processFireBalls();
        }

        int answer = getFireBallMass();
        System.out.println(answer);
    }

    private static void moveFireBalls() {
        int size = FireBalls.size();

        for (int i = 0; i < size; i++) {
            FireBall fireBall = FireBalls.poll();
            int nextRow = (fireBall.row + RowDirections[fireBall.direction] * fireBall.velocity) % N;
            int nextColumn = (fireBall.column + ColumnDirections[fireBall.direction] * fireBall.velocity) % N;

            if (nextRow < 0)    nextRow += N;
            if (nextColumn < 0) nextColumn += N;

            fireBall.row = nextRow;
            fireBall.column = nextColumn;
            Field[nextRow][nextColumn].add(fireBall);
        }
    }

    private static void processFireBalls() {
        for (int row = 0; row < N; row++) {
            for (int column = 0; column < N; column++) {
                // 같은 곳에 파이어볼 개수가 2개 미만인 경우 -> 현재 존재하는 파이어볼을 관리하는 큐(FireBalls)에 넣어주기
                if (Field[row][column].size() == 1) {
                    FireBalls.add(Field[row][column].poll());
                }

                // 같은 곳에 파이어볼 개수가 2개 이상인 경우 -> 4개로 분리
                else if (Field[row][column].size() > 1) {
                    splitFireBalls(row, column);
                }
            }
        }
    }

    private static void splitFireBalls(int row, int column) {
        int sumMass = 0, sumVelocity = 0, size = Field[row][column].size();
        boolean isAllEven = true, isAllOdd = true;

        while (!Field[row][column].isEmpty()) {
            FireBall fireBall = Field[row][column].poll();
            sumMass += fireBall.mass;
            sumVelocity += fireBall.velocity;

            if (fireBall.direction % 2 == 0)    isAllOdd = false;
            else                                isAllEven = false;
        }

        int newMass = sumMass / 5;
        int newVelocity = sumVelocity / size;

        if (newMass > 0) {
            for (int i = 0; i < 4; i++) {
                int newDirection = (isAllEven || isAllOdd) ? i * 2 : i * 2 + 1;
                FireBalls.add(new FireBall(row, column, newMass, newVelocity, newDirection));
            }
        }
    }

    private static int getFireBallMass() {
        int result = 0;

        for (FireBall fireBall : FireBalls) {
            result += fireBall.mass;
        }

        return result;
    }

    private static void initialize() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] args = br.readLine().split(" ");

        N = Integer.parseInt(args[0]);
        M = Integer.parseInt(args[1]);
        K = Integer.parseInt(args[2]);
        Field = new LinkedList[N][N];
        FireBalls = new LinkedList<>();

        // 1. 2차원 배열 각 요소마다 큐(Queue) 생성
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                Field[r][c] = new LinkedList<FireBall>();
            }
        }

        // 2. 현재 존재하는 파이어볼 정보를 담는 FireBalls 큐에 초기값 넣기
        for (int i = 0; i < M; i++) {
            args = br.readLine().split(" ");
            int row = Integer.parseInt(args[0]) - 1;
            int column = Integer.parseInt(args[1]) - 1;
            int mass = Integer.parseInt(args[2]);
            int velocity = Integer.parseInt(args[3]);
            int direction = Integer.parseInt(args[4]);

            FireBalls.add(new FireBall(row, column, mass, velocity, direction));
        }

        br.close();
    }
}