[BOJ 20056] 마법사 상어와 파이어볼 - JAVA, Gold4

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

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

 

📌구현할 기능 목록📌

1. 파이어볼 객체를 구현할 클래스를 작성한다.

 - 행 위치, 열 위치, 질량, 속도, 이동방향 값을 저장할 필드를 가진다.

 

2. 각 위치를 나타내는 격자를 N x N 크기의 삼중 ArrayList로 생성한다.

 - ArrayList<ArrayList<ArrayList<Fireball>>> map = new ArrayList<>();

 - 마지막 ArrayList에서 Fireball 객체를 저장하면서, 특정 위치에 존재하는 파이어볼들을 알 수 있다.

 

3. 사용자로부터 N(맵의 크기), M(파이어볼 개수), K(이동 횟수)를 입력받는다.

 

4. 사용자로부터 M개의 파이어볼의 상태값을 입력받고 객체를 생성한다.

 - 입력받은 위치에 대응되는 map에 생성한 객체를 추가한다.

 

5. map 좌표 전체를 탐색하면서, 해당 위치의 Fireball을 각 객체 스펙에 맞게 이동시킨다.

 - 각 객체가 이동한 위치를 모두 저장하는 tempMap 삼중 ArrayLIst를 생성하고, 맵 이동 후 map에 복사한다.

 - N x N 크기의 map ArrayList는 0번 인덱스와 N-1 인덱스가 행과 열끼리 모두 연결되어있다.

   따라서 이에 알맞는 이동을 하도록 조정해야한다.

 

6. map 의 특정 좌표에 위치한 Fireball 객체가 2개 이상인 경우, Fireball을 합치고 다시 4개의 객체로 나누는 메서드를 작성한다.

 - Fireball 객체들이 가진 값을 모두 합한 값들을 구한다.

 - map 해당 좌표에 있던 모든 객체를 삭제한다.

 - 하나로 합친 객체를 4개로 나눈 각 객체의 질량이 0이면 객체를 생성하지 않고, 

   질량이 0이 아니라면 해당 좌표 map에 4개의 객체를 생성한다.

 - 새로운 객체 생성 시, 방향은 조건에 따라 기존 합쳐지는 모든 객체의 방향이 홀수 또는 짝수면 0,2,4,6으로

   그게 아니면 1,3,5,7로 설정되도록 한다.

 

7. map에 존재하는 Fireball 객체의 모든 질량 합을 구하는 메서드를 작성한다.

 

💻코드 적용💻

1. 파이어볼 객체를 구현할 클래스를 작성한다.

static class Fireball{
    int row;
    int column;
    int mass;
    int speed;
    int direction;

    public Fireball(int row, int column, int mass, int speed, int direction) {
        this.row = row;
        this.column = column;
        this.mass = mass;
        this.speed = speed;
        this.direction = direction;
    }
}

 

 

2. 각 위치를 나타내는 격자를 N x N 크기의 삼중 ArrayList로 생성한다.

static ArrayList<ArrayList<ArrayList<Fireball>>> map = new ArrayList<>();

/////////////////////////////////////////////////////////////////////////

for(int i=0;i<N;++i){
    map.add(new ArrayList<>());
    for(int j=0;j<N;++j){
        map.get(i).add(new ArrayList<>());
    }
}

 

 

3. 사용자로부터 N(맵의 크기), M(파이어볼 개수), K(이동 횟수)를 입력받는다.

StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());

 

 

4. 사용자로부터 M개의 파이어볼의 상태값을 입력받고 객체를 생성한다.

for(int i=0;i<M;++i){
    st = new StringTokenizer(br.readLine());
    int row = Integer.parseInt(st.nextToken())-1;
    int column = Integer.parseInt(st.nextToken())-1;
    int mass = Integer.parseInt(st.nextToken());
    int speed = Integer.parseInt(st.nextToken());
    int direction = Integer.parseInt(st.nextToken());
    Fireball fireball = new Fireball(row,column,mass,speed,direction);
    map.get(row).get(column).add(fireball);
}

 

 

5. map 좌표 전체를 탐색하면서, 해당 위치의 Fireball을 각 객체 스펙에 맞게 이동시킨다.

static void moveFireball(){
    ArrayList<ArrayList<ArrayList<Fireball>>> tempMap = new ArrayList<>();
    for(int i=0;i<N;++i){
        tempMap.add(new ArrayList<>());
        for(int j=0;j<N;++j){
            tempMap.get(i).add(new ArrayList<>());
        }
    }

    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            for(Fireball fireball:map.get(i).get(j)){
                int mx = fireball.row + dx[fireball.direction]* (fireball.speed%N);
                int my = fireball.column + dy[fireball.direction]* (fireball.speed%N);

                if(mx<0) mx+=N;
                if(my<0) my+=N;
                mx%=N;
                my%=N;

                tempMap.get(mx).get(my).add(new Fireball(mx,my, fireball.mass, fireball.speed, fireball.direction));
            }
        }
    }
    map=tempMap;
}

여기서 주의할 점은 tempMap을 별도로 생성해야한다는 점이다.

이유는 파이어볼 객체가 이동한 결과를 map에 곧바로 적용시키면,

2중 반복문을 통해 map을 탐색하다가 이미 이동했던 객체를 또 이동시키게 될 수 있기 때문이다.

 

또 하나 주의할 점은 특정 파이어볼의 이동 후 행과 열의 위치를 나타내는 mx와 my를 구할 때로,

0번 인덱스와 N-1번의 인덱스가 서로 연결되어 있으므로

mx, my가 0보다 작으면 N을 더해 이동 후 위치를 맞추고,

mx, my가 N보다 같거나 큰 경우 IndexOutOfBounds가 발생하지 않도록 N으로 나머지를 구해줘야한다.

 

또 mx, my를 구할 때 사용하는 speed도 N으로 나눈 나머지를 구한뒤 연산에 사용해야 하는데,

이는 N=4, fireball.row =0, dx[fireball.direction]=6 (←왼쪽 방향), speed=197이라고 할 때

 

1) speed를 N으로 나누어 나머지로 만들지 않은 경우

mx = fireball.row + dx[fireball.direction]* fireball.speed = 0+(-1)*200 = -197

mx<0 이므로 mx = mx + N = -197 + 4 = -193

mx%=N = -1

이 나오고(0보다 작아 후에 IndexOutOfBounds 발생함)

 

2) speed를 N으로 나누어 나머지로 만들어 연산에 사용한 경우

mx = fireball.row + dx[fireball.direction]* (fireball.speed%4) = 0+(-1)*1 = -1

mx<0 이므로 mx = mx + N = -1 + 4 = 3

mx%=N = 3

 

으로 나오기 때문에 speed를 N으로 나눈 나머지로 변환 후 연산에 사용해야 한다.

 

6. map 의 특정 좌표에 위치한 Fireball 객체가 2개 이상인 경우, Fireball을 합치고 다시 4개의 객체로 나누는 메서드를 작성한다.

static int sameDirection[] = {0,2,4,6};
static int otherDirection[] = {1,3,5,7};
////////////////////////////////////////

static void unionFireball(){
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            if(map.get(i).get(j).size()>=2){
                int mass=0;
                int speed=0;
                int size = map.get(i).get(j).size();
                boolean isAllOddOrEven= true;
                int divideValue = map.get(i).get(j).get(0).direction%2;
                for(Fireball fireball:map.get(i).get(j)){
                    mass+= fireball.mass;
                    speed+= fireball.speed;
                    if(fireball.direction%2!=divideValue) isAllOddOrEven=false;
                }

                map.get(i).get(j).clear();
                if(mass/5!=0){
                    for(int k=0;k<4;++k){
                        if(isAllOddOrEven){
                            map.get(i).get(j).add(new Fireball(i,j,mass/5,speed/size,sameDirection[k]));
                        }
                        else{
                            map.get(i).get(j).add(new Fireball(i,j,mass/5,speed/size,otherDirection[k]));
                        }
                    }
                }
            }
        }
    }
}

isAllOddOrEven 변수를 사용해, 합쳐지는 파이어볼 객체들의 방향이 모두 짝수거나 홀수면 0,2,4,6이,

모두 짝수거나 홀수이지 않으면 1,3,5,7의 방향으로 새로운 파이어볼 객체가 4개 생성되도록 한다.

(나누어지는 파이어볼의 질량이 0이면 새로운 파이어볼 객체를 생성하지 않도록 했다.)

 

7. map에 존재하는 Fireball 객체의 모든 질량 합을 구하는 메서드를 작성한다.

static int calculateSumResult(){
    int sum=0;
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            for(Fireball fireball:map.get(i).get(j)){
                sum+= fireball.mass;
            }
        }
    }
    return sum;
}

 

⌨제출한 코드⌨

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<ArrayList<ArrayList<Fireball>>> map = new ArrayList<>();
    static int N,M,K;
    static int dx[] = {-1,-1,0,1,1,1,0,-1};
    static int dy[] = {0,1,1,1,0,-1,-1,-1};
    static int sameDirection[] = {0,2,4,6};
    static int otherDirection[] = {1,3,5,7};
    static class Fireball{
        int row;
        int column;
        int mass;
        int speed;
        int direction;

        public Fireball(int row, int column, int mass, int speed, int direction) {
            this.row = row;
            this.column = column;
            this.mass = mass;
            this.speed = speed;
            this.direction = direction;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;++i){
            map.add(new ArrayList<>());
            for(int j=0;j<N;++j){
                map.get(i).add(new ArrayList<>());
            }
        }

        for(int i=0;i<M;++i){
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken())-1;
            int column = Integer.parseInt(st.nextToken())-1;
            int mass = Integer.parseInt(st.nextToken());
            int speed = Integer.parseInt(st.nextToken());
            int direction = Integer.parseInt(st.nextToken());
            Fireball fireball = new Fireball(row,column,mass,speed,direction);
            map.get(row).get(column).add(fireball);
        }

        for(int k=0;k<K;++k){
            moveFireball();
            unionFireball();
        }

        bw.write(calculateSumResult()+"\n");
        bw.flush();
        bw.close();
    }

    static void moveFireball(){
        ArrayList<ArrayList<ArrayList<Fireball>>> tempMap = new ArrayList<>();
        for(int i=0;i<N;++i){
            tempMap.add(new ArrayList<>());
            for(int j=0;j<N;++j){
                tempMap.get(i).add(new ArrayList<>());
            }
        }

        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                for(Fireball fireball:map.get(i).get(j)){
                    int mx = fireball.row + dx[fireball.direction]* (fireball.speed%N);
                    int my = fireball.column + dy[fireball.direction]* (fireball.speed%N);

                    if(mx<0) mx+=N;
                    if(my<0) my+=N;
                    mx%=N;
                    my%=N;

                    tempMap.get(mx).get(my).add(new Fireball(mx,my, fireball.mass, fireball.speed, fireball.direction));
                }
            }
        }
        map=tempMap;
    }

    static void unionFireball(){
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                if(map.get(i).get(j).size()>=2){
                    int mass=0;
                    int speed=0;
                    int size = map.get(i).get(j).size();
                    boolean isAllOddOrEven= true;
                    int divideValue = map.get(i).get(j).get(0).direction%2;
                    for(Fireball fireball:map.get(i).get(j)){
                        mass+= fireball.mass;
                        speed+= fireball.speed;
                        if(fireball.direction%2!=divideValue) isAllOddOrEven=false;
                    }

                    map.get(i).get(j).clear();
                    if(mass/5!=0){
                        for(int k=0;k<4;++k){
                            if(isAllOddOrEven){
                                map.get(i).get(j).add(new Fireball(i,j,mass/5,speed/size,sameDirection[k]));
                            }
                            else{
                                map.get(i).get(j).add(new Fireball(i,j,mass/5,speed/size,otherDirection[k]));
                            }
                        }
                    }
                }
            }
        }
    }

    static int calculateSumResult(){
        int sum=0;
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                for(Fireball fireball:map.get(i).get(j)){
                    sum+= fireball.mass;
                }
            }
        }
        return sum;
    }
}