[boj] 백준 20056 마법사 상어와 파이어볼 (Java) - 시뮬레이션

[문제]

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

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

 

[풀이]

1. 파이어볼이 d 방향으로 s만큼 이동한다.

2. 같은 칸에 2개 이상의 파이어볼이 있다면 합쳐진 후 4개로 나눠진다.

3. 이렇게 k번 이동한다.

 

처음에는 파이어볼을 이동시키기 위해서 board[][] 배열에 파이어볼을 저장한 후 add와 remove를 사용했으나 이 경우 remove 때문에 인덱스가 변경되어 배열 접근 시 오류가 쉽게 발생한다.

따라서 파이어볼을 이동시킬 때마다 새로운 board[][] 배열을 생성해서 이동시키고, 그 board 배열에 대해서 파이어볼을 합치고 나눌때도 새로운 board[r][c] 배열을 생성해서 나눠진 파이어볼을 새로 추가시킨다. 파이어볼을 관리하는 ArrayList도 새로 생성해서 관리하도록 하였다.

 

파이어볼을 이동시킬 때 배열의 범위를 벗어나지 않도록 주의해야 한다.

파이어볼은 d 방향으로 s만큼 이동한다. 이때 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다는 의미는 n을 넘어서면 다시 1로 돌아온다는 것을 의미한다. 

만약에 3x3 배열이 있고 1번 열에 있던 파이어볼이 3만큼 이동한다면 다시 1번 열로 돌아온다. 이는 s%n 만큼 이동함을 의미한다.

그런데 만약 2번 열에 있던 파이어볼이 5만큼 이동한다면 5%3=2만큼 이동하는데 이는 4로 범위를 벗어난다. 실제로는 1번 열에 위치할 것이고 범위를 초과할 경우 n만큼 뺀 값이 실제 위치가 된다.

따라서 n을 초과하는 행이나 열에 대해서는 -n을, 1보다 작은 행이나 열에 대해서는 +n을 해주면 실제 파이어볼이 이동하는 좌표를 구할 수 있다.

 

[코드]

 

package 시뮬레이션;

import java.util.*;
import java.io.*;

public class boj_20056_java {
    static int n, m, k;
    static List<FireBall>[][] board;
    static List<FireBall> balls;
    static int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dc = {0, 1 ,1 ,1, 0, -1, -1, -1};
    public static class FireBall{
        int r, c, m, s, d;
        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;
        }
    }
    public static void main(String[] args) throws Exception{
        //마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.
        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());

        board = new ArrayList[n+1][n+1];
        balls = new ArrayList<>();
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                board[i][j] = new ArrayList<>();
            }
        }

        for(int i=0; i<m; i++){
            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()); 
            board[r][c].add(new FireBall(r, c, m, s, d));
            balls.add(new FireBall(r, c, m, s, d));
           
        }

        while(k-->0){

            //모든 파이어볼이 d방향으로 이동
            moveFireBall();


            //파이어볼 합치고 나누기
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(board[i][j].size()>=2){
                        combineAndDivide(i, j, board[i][j]);
                    }
                }
            }

            //FireBall list 정리
            cleanList();
        }

        int answer = 0;
        for(FireBall ball:balls){
            answer += ball.m;
        }

        System.out.println(answer);

    }

    public static void cleanList(){
        balls = new ArrayList<>();
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(board[i][j].size()>0){
                    for(FireBall b:board[i][j]){
                        balls.add(b);
                    }
                }
            }
        }
    }

    public static void moveFireBall(){

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                board[i][j] = new ArrayList<>();
            }
        }

        for(FireBall ball:balls){

            int nr = ball.r + dr[ball.d]*(ball.s%n);
            int nc = ball.c + dc[ball.d]*(ball.s%n); //si칸만큼 이동

            if(nr<=0) nr += n;
            if(nc<=0) nc += n;
            if(nr>n) nr -= n;
            if(nc>n) nc -= n;

            ball.r = nr;
            ball.c = nc;
            board[nr][nc].add(ball);       
        }
        
    }

    public static void combineAndDivide(int r, int c, List<FireBall> balls){
        //질량, 속도, 개수, 모두 홀수인지 짝수인지 확인
        
        //합치기
        int m_sum = 0, s_sum = 0;
        boolean isEven = true;
		boolean isOdd = true;
        for(FireBall b:balls){
            m_sum += b.m;
            s_sum += b.s;
            if(b.d%2 == 0) {
				isOdd = false;
			} else {
				isEven = false;
			}

        }

        int nm = m_sum/5;
        int ns = s_sum/balls.size();
        int[] dirs = {0, 2, 4, 6};
        if(!isOdd && !isEven){
            dirs[0] = 1; dirs[1] = 3; dirs[2] = 5; dirs[3] = 7;
        }
    
    
        //4개의 파이어볼로 나눠짐
        board[r][c] = new ArrayList<>();
        if(nm<=0) return;
        for(int d:dirs){
            board[r][c].add(new FireBall(r, c, nm, ns, d));
        }
    }
}