Java/코딩테스트

백준 20056

Bubbles 2023. 10. 10. 18:51

🔥 백준 20056 : 마법사 상어와 파이어볼 

https://www.acmicpc.net/problem/20056

 

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

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치

www.acmicpc.net

🔥 삼성 기출인 상어 시리즈 문제이다. 

🔥 파이어볼 클래스를 하나 만들고, 위치 정보 + 방향, 속력, 질량을 필드로 선언해주었다. 

private static class Fireball {
    int x;
    int y;
    int mass;
    int speed;
    int dir;

    public Fireball(int x, int y, int m, int s, int d) {
        this.x = x;
        this.y = y;
        this.mass = m;
        this.speed = s;
        this.dir = d;
    }
}

 

 

🔥 구현해야할 기능 

  • 각 파이어볼들을 이동 시켜주기 : moveFireball()
  • map을 보고, 파이어볼 2개 이상인 칸이라면 파이어볼들을 합쳐주기 : joinFireball()
    • 이때 단순 질량과 속도는 합한다음 나눠주면 되는데, 문제는 방향이다.
    • 마법사 상어와 복제마법처럼 모든 방향이 다 필요한 건 아니고, 각 방향이 다 짝수 || 홀수인지만 파악하면된다. 
    • 따라서 방향까지 저장하는 3차원 배열을 만들되, int [size][size][2]로 선언해주었다. 방향이 짝수인 파이어볼, 홀수인 파이어볼 각 개수들만 카운트해두면 된다. 
  • 합쳐진 파이어볼들을 나눠주기 : divideFireball() 
    • 위에서 계산한 질량, 속도, 방향 기준으로 파이어볼 4개로 다시 만들어주면 된다. 
  • 그 외, 이 파이어볼은 맵을 벗어나게 이동한다면 재조정이 된다. : rePos()  
    • 예를 들어 (0, 0)에서 위로 2칸 이동하면 (-2, 0)이 되는데, 4*4 사이즈 맵에서는 이를 (2, 0)로 조정해줘야 한다.
    • 이 재조정을 위한 메소드도 구현해두어야 한다. 

🔥 각 함수들은 아래와 같은 순서로 호출된다.

private static void magic() {
    moveFireball();
    joinFireball();
    divideFireball();
}

🔥 파이어볼 움직이기 

private static void moveFireball() {
    List<Fireball> list = new ArrayList<>();
    for (Fireball f : fireballs) {
        int nextX = f.x + (dirX[f.dir] * f.speed);
        nextX = rePos(nextX);
        int nextY = f.y + (dirY[f.dir] * f.speed);
        nextY = rePos(nextY);
        list.add(new Fireball(nextX, nextY, f.mass, f.speed, f.dir));
    }
    fireballs = list;
}

🔥 이 때 rePos 함수를 통해 맵의 범위를 벗어난 경우에 재조정을 해준다.

rePos는 아래와 같다. 

private static int rePos (int pos) {
    int temp = pos;
    if (pos >= size) {
        temp = (pos % size);
    }
    else if (pos < 0){
        if (Math.abs(temp) % size == 0) {
            temp = 0;
        } else {
            int left = Math.abs(temp) / size + 1;
            temp += (left * size);
        }
    }
    return temp;
}

 

🔥 rePos 함수 작동 원리 

  • 양수인 경우에는 그냥 size로 나눈 나머지로 재조정을 해주면 된다.
  • 음수인 경우에는, 절대값으로 바꾼 후, 계산을 해줘야 한다. 
    • 절대값으로 바꾸고 size로 나눈 나머지가 0이라면 안 움직이면 된다.
    • 그 외에는 절대값으로 바꾼 값 / size + 1 을 해준다음 원래의 마이너스 값에 더해주면 된다 .
  • 4 * 4 사이즈 라고 생각하며 계산해보았다. 예시를 보면 무슨 규칙인지 이해가 될 것이다. 
바뀌기 전 바꾼 후 바뀌기 전 바꾼 후
-1 +3 
1 % 4 == 1이므로, 0이 아니다. 
      1 / 4 + 1 = 1
-3 + ( 4 * 1 ) = 3 		 -5 +3
-2 +2 -6 +2
-3 +1 -7 +1
7 % 4 == 3이므로, 0이 아님
       7 / 4 + 1 = 2
-7 + (4 * 2) = 1
-4 +0
4 % 4 == 0 
절대값으로 바꾸고 남은 나머지가 0이므로 0		 -8 +0

🔥 파이어볼 합치기

만약 현재 map이 빈칸이라면 그냥 넣기

map에 이미 fireball이 존재한다면 기존의 fireball과 합친다. 

사실 이때, 굳이 좌표정보를 넣지 말고 그냥 mass, speed, direction만 모은 클래스를 만들었다면 좀 더 효율적으로 코드를 만들 수 있었을 것 같다. 

쨋든 그렇게 합치고, 각 방향별로 짝수 방향이면 dir[x][y][0]의 count를, 홀수방향이라면 dir[x][y][1]의 count를 늘린다. 

private static void joinFireball() {
    map = new Fireball[size][size];
    dir = new int[size][size][2]; // 각 방향들만 저장하는 용도
    for (Fireball f : fireballs) {
        if (map[f.x][f.y] == null) {
            map[f.x][f.y] = f;
        }
        else {
            map[f.x][f.y] = new Fireball(
                    f.x, f.y,
                    f.mass + map[f.x][f.y].mass,
                    f.speed + map[f.x][f.y].speed,
                    f.dir
            );

        }
        if (f.dir % 2 == 0) {
            dir[f.x][f.y][0]++;
        } else {
            dir[f.x][f.y][1]++;
        }
    }
}

 

 

🔥 합쳐진 파이어볼 다시 나눠주기 : divideFireball()  

나눠주기 전에 count 변수로 각 칸에 몇 개의 파이어볼이 합쳐진 것인지 먼저 판단한다. count >=2인 경우만 나눠서 발산해줘야하므로! 

그다음 index 변수로 방향을 1-3-5-7로 갈지, 0-2-4-6으로 갈지 설정한다.

그리고 map에서 칸이 null이 아닌 경우에 한정하여

  • count >= 2라면 mass, speed 계산해준다음 앞에서 구한 index += 2대로 fireball 리스트에 담아준다. 
  • count 1인 경우는 mass speed 재 계산 없이 바로 리스트에 더해주면 된다. 
private static void divideFireball() {
    fireballs = new ArrayList<>();
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            int count = dir[i][j][0] + dir[i][j][1];
            int index = 1;
            if (dir[i][j][0] == 0 || dir[i][j][1]==0) {
                index = 0; // 짝수 방향으로 가야 하는 경우
            }

            if (map[i][j] != null) {
                if (count >= 2) {
                    int mass = (int) Math.floor((double) map[i][j].mass / 5.0);
                    int speed = (int) Math.floor((double) map[i][j].speed / count);

                    if (mass != 0) {
                        for (int k = index; k < 8; k+=2) {
                            fireballs.add(new Fireball(i,j, mass, speed, k));
                        }
                    }
                } else {
                    fireballs.add(map[i][j]);
                }

            }
        }
    }
}

 

 

🔥 이 과정을 다 거친 후, 마지막으로 fireball(파이어볼을 담는 리스트) 돌면서 질량들만 쭉 더해주면 된다.

for (Fireball fireball : fireballs) {
    answer += fireball.mass;
}

 

 

🔥 전체코드 

import java.io.*;
import java.util.*;
public class p20056 {
    static int dirX[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
    static int dirY[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
    static int size, fire, practice;
    static Fireball[][] map;
    static int[][][] dir;
    static List<Fireball> fireballs;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        size = Integer.parseInt(st.nextToken());
        fire = Integer.parseInt(st.nextToken());
        practice = Integer.parseInt(st.nextToken());
        fireballs = new ArrayList<>();
        map = new Fireball[size][size];

        for (int i = 0; i < fire; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            fireballs.add(new Fireball(x-1, y-1, m, s, d));
        }

        for (int i = 0; i < practice; i++) {
            magic();
        }

        int answer = 0;
        for (Fireball fireball : fireballs) {
            answer += fireball.mass;
        }

        System.out.println(answer);
    }

    private static void magic() {
        moveFireball();
        joinFireball();
        divideFireball();
    }

    private static void divideFireball() {
        fireballs = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                int count = dir[i][j][0] + dir[i][j][1];
                int index = 1;
                if (dir[i][j][0] == 0 || dir[i][j][1]==0) {
                    index = 0; // 짝수 방향으로 가야 하는 경우
                }

                if (map[i][j] != null) {
                    if (count >= 2) {
                        int mass = (int) Math.floor((double) map[i][j].mass / 5.0);
                        int speed = (int) Math.floor((double) map[i][j].speed / count);

                        if (mass != 0) {
                            for (int k = index; k < 8; k+=2) {
                                fireballs.add(new Fireball(i,j, mass, speed, k));
                            }
                        }
                    } else {
                        fireballs.add(map[i][j]);
                    }

                }
            }
        }
    }
    private static void joinFireball() {
        map = new Fireball[size][size];
        dir = new int[size][size][2]; // 각 방향들만 저장하는 용도
        for (Fireball f : fireballs) {
            if (map[f.x][f.y] == null) {
                map[f.x][f.y] = f;
            }
            else {
                map[f.x][f.y] = new Fireball(
                        f.x, f.y,
                        f.mass + map[f.x][f.y].mass,
                        f.speed + map[f.x][f.y].speed,
                        f.dir
                );

            }
            if (f.dir % 2 == 0) {
                dir[f.x][f.y][0]++;
            } else {
                dir[f.x][f.y][1]++;
            }
        }
    }

    private static void moveFireball() {
        List<Fireball> list = new ArrayList<>();
        for (Fireball f : fireballs) {
            int nextX = f.x + (dirX[f.dir] * f.speed);
            nextX = rePos(nextX);
            int nextY = f.y + (dirY[f.dir] * f.speed);
            nextY = rePos(nextY);
            list.add(new Fireball(nextX, nextY, f.mass, f.speed, f.dir));
        }
        fireballs = list;
    }

    private static int rePos (int pos) {
        int temp = pos;
        if (pos >= size) {
            temp = (pos % size);
        }
        else if (pos < 0){
            if (Math.abs(temp) % size == 0) {
                temp = 0;
            } else {
                int left = Math.abs(temp) / size + 1;
                temp += (left * size);
            }
        }
        return temp;
    }

    private static class Fireball {
        int x;
        int y;
        int mass;
        int speed;
        int dir;

        public Fireball(int x, int y, int m, int s, int d) {
            this.x = x;
            this.y = y;
            this.mass = m;
            this.speed = s;
            this.dir = d;
        }
    }
}