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

📖 문제

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

 

 

💡  풀이 방식

• 구현, 시뮬레이션

필요 자료구조
- 파이어볼 이동 시 정보 (2차원 ArrayList 배열 !!)
- 모든 파이어볼 정보 저장할 ArrayList

 

1. 파이어볼 정보 저장용 리스트에 파이어볼 정보를 저장한다.

2. K번 이동시키고, 파이어볼을 분열시킨다.

   2-1) [파이어볼 이동] 반복문을 통해 리스트에 있는 파이어볼들의 위치를 이동시키고, 파이어볼 이동 시 정보를 나타내는 2차원 리스트 배열 map의 새 위치에 현재 객체를 저장한다.

 

   2-2) [파이어볼 분열] 2차원 for문을 통해 모든 좌표를 돌며 파이어볼 갯수가 2개 미만인 경우, map[i][j]에 있는 원소를 모두 제거한다. / 파이어볼 갯수가 2개 이상인 경우, 분열을 진행한다.

 

3. 리스트에 있는 파이어볼들의 질량의 합을 구한다.

 

 

 

 

💥 유의사항

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
    
    static int N,M,K;
    static List<Fireball>[][] map;  // 파이어볼 이동 시 정보 (⭐ 2차원 리스트 배열!!)
    static List<Fireball> list = new ArrayList<>(); // 모든 파이어볼 정보
    
    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());
        
        map = new ArrayList[N][N];  // 2차원 ArrayList 배열!!
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++)
                map[i][j] = new ArrayList<>();
        }
        
        while(M --> 0) {
            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());
            
            list.add(new Fireball(r-1,c-1,m,s,d));
        }
        
        while(K --> 0) {
            move();
            fire();
        }
        
        int answer = 0;
        for(Fireball fb : list)
            answer += fb.m;
        
        System.out.println(answer);
    }
    
    // 1. 파이어볼 이동 메서드
    private static void move() {
        for(Fireball fb : list) {
            int nx = (fb.r + dx[fb.d] * (fb.s%N) + N) % N;
            int ny = (fb.c + dy[fb.d] * (fb.s%N) + N) % N;
            
            fb.r = nx;
            fb.c = ny;
            
            map[fb.r][fb.c].add(fb);
        }
    }
    
    // 2. 파이어볼 분열 메서드
    private static void fire() {
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                // 파이어볼 갯수가 2개 미만인 경우
                if(map[i][j].size() < 2) { 
                    map[i][j].clear();
                    continue;
                }
                
                // 파이어볼 갯수가 2개 이상인 경우
                int mSum = 0, sSum = 0;
                int oddCnt = 0, evenCnt = 0;
                int size = map[i][j].size();
                
                // 분열 진행
                for(Fireball fb : map[i][j]) {
                    mSum += fb.m;
                    sSum += fb.s;
                    
                    if(fb.d % 2 == 1)   oddCnt++;
                    else                evenCnt++;
                    
                    list.remove(fb);    // 💥 분열된 파이어볼 제거
                }
                map[i][j].clear();
                
                mSum /= 5;  // 분열된 질량 구하기
                if(mSum == 0)   continue; // 질량이 0인 파이어볼은 소멸되어 없어짐
                
                sSum /= size;   // 분열된 속도 구하기
                
                // 모든 파이어볼 방향이 짝수이거나 홀수인 경우
                if(oddCnt == size || evenCnt == size) {
                    for(int x = 0 ; x < 8 ; x += 2) // 0,2,4,6 방향 분열
                        list.add(new Fireball(i, j, mSum, sSum, x));
                }
                else {
                    for(int x = 1 ; x < 8 ; x += 2) // 1,3,5,7 방향 분열
                        list.add(new Fireball(i, j, mSum, sSum, x));
                }
            }
        }
    }
}
 
class Fireball {
    int r, c, m, s, d;
    
    public Fireball(int r, int c, int m, int s, int d) {
        this.r = r;
        this.c = c;
        this.m = m;
        this.s = s;
        this.d = d;
    }
}
 

 

 

 

➕ 다른 풀이 방식

3차원 map과 큐를 활용하신 풀이

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

 

---

💦 어려웠던 점

- 2차원 배열 좌표 리스트로 값을 저장하고 싶은데 어떻게 해야하지?의 문제..

 

🧐 새로 알게 된 내용

- List<Fireball>[][] map : 2차원 ArrayList 배열...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준] 알고리즘 분류(구현,JAVA)20056번, 마법사 상어와 파이어볼