[백준/BOJ] 20056 마법사 상어와 파이어볼 (Java)

Binary Code

[백준/BOJ] 20056 마법사 상어와 파이어볼

[풀이]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    static class Fire {
        int r,c,m,s,d;
        int cnt;
        int all; // 0:기타 1:홀 -1:짝
        public Fire(int r, int c, int m, int s, int d, int cnt, int all) {
            super();
            this.r = r;
            this.c = c;
            this.m = m;
            this.s = s;
            this.d = d;
            this.cnt = cnt;
            this.all = all;
        }
    }
    private static ArrayList<Fire> list;
    private static int N, M, K;
    private static int[] dx = {-1,-1,0,1,1,1,0,-1};
    private static int[] dy = {0,1,1,1,0,-1,-1,-1};
    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());
        list = new ArrayList<Fire>();
        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());
            Fire fire = null;
            if(d%2==0) fire = new Fire(r,c,m,s,d,1,-1);
            else if(d%2==1) fire = new Fire(r,c,m,s,d,1,1);
            list.add(fire);
        }
        int ans = 0;
        while(true) {
            Fire[][] map = new Fire[N+1][N+1];
            // 1.이동
            move(map);            
            // 2.같은 칸 합치기 & 조건에 따라 4개로 파이어볼로 나누기
            Merge(map);
            
            if(--K == 0) break;
        }
        for(int i=0; i<list.size(); i++)
            ans += list.get(i).m;
        System.out.println(ans);
    }
    private static void move(Fire[][] map) {
        int size = list.size();
        while(size-->0) {
            Fire temp = list.get(0); list.remove(0);
            // r,c,m,s,d,cnt,all(짝홀/기타)
            int r = temp.r;
            int c = temp.c;
            int d = temp.d;
            int s = temp.s;
            // 다음 좌표만 구하면 된다
            // 1~N
            int speed = s%N;
             r = r + dx[d] * speed;
            c = c + dy[d] * speed;
            if(r > N) r -= N;
            if(c > N) c -= N;
            if(r < 1) r += N;
            if(c < 1) c += N;
            temp.r = r; temp.c = c;
            if(map[r][c]==null) map[r][c] = temp;
            else {
                map[r][c].m += temp.m;
                map[r][c].s += temp.s;
                map[r][c].cnt++;
                if(d%2==0 && map[r][c].all != -1) { // 짝 && 먼저 위치한 파이어볼이 짝 X
                    map[r][c].all = 0;
                }else if(d%2==1 && map[r][c].all != 1) { // 홀 && 먼저 위치한 파이어볼이 홀 X
                    map[r][c].all = 0;
                }
            }
        }
    }
    private static void Merge(Fire[][] map) {
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(map[i][j] !=null) {
                    if(map[i][j].cnt==1) {         // 한 개
                        list.add(map[i][j]);
                    }else if(map[i][j].cnt>1) { // 여러개 
                        int m = map[i][j].m/5;  // 질량=질량의합/5
                        if(m==0) continue;    // 질량 0 소멸
                        
                        int s = map[i][j].s/map[i][j].cnt; // 속도=속도의합/개수
                        if(map[i][j].all==0) {// !(모두 짝||모두 홀)
                            for(int k=0; k<4; k++)
                                list.add(new Fire(i, j, m, s, k*2+1, 1, 1));
                        }else {
                            for(int k=0; k<4; k++)
                                list.add(new Fire(i, j, m, s, k*2, 1, -1));
                        }
                    }
                }
            }
        }
    }
}