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

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

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

 

문제

어른 상어가 마법사가 되었고, 파이어볼을 배웠다.

마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다.

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.

파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.

7 0 1
6 X 2
5 4 3

마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.

1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.

 

입력

첫째 줄에 N, M, K가 주어진다.

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

서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.

 

출력

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.

 

---

소스코드

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

class Main {
    //파이어볼 정보 클래스
    static class meteor{
        //행, 열, 질량, 속도, 방향
        int r, c, m, s, d;
        public meteor(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;
        }
    }
    static int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};	//방향 r값 변경값
    static int[] dc = {0, 1, 1, 1, 0, -1, -1, -1};	//방향 c값 변경값
    static ArrayList<meteor>[][] map;	//파이어볼 이동했을 때 정보
    static ArrayList<meteor> meteors = new ArrayList<>();	//모든 파이어볼 정보
    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(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        map = new ArrayList[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                map[i][j] = new ArrayList<>();
        }
        //입력되는 파이어볼 정보 저장
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int m = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            meteors.add(new meteor(r, c, m, s, d));
        }

        //K번 이동명령 진행
        for (int i = 0; i < K; i++) {
            meteorMove(N);
            meteorFire(N);
        }

        bw.write(meteorCal() + "");
        bw.flush();
        bw.close();
        br.close();
    }

    //파이어볼 이동
    static void meteorMove(int N) {
        for (meteor cur : meteors) {
            //r, c값 변경
            // +N을 하는 이유는 이동하였을 때 음수가 나올 수 있기 때문입니다.
            int tempR = (cur.r + N + dr[cur.d] * (cur.s%N)) % N;
            int tempC = (cur.c + N + dc[cur.d] * (cur.s%N)) % N;
            cur.r = tempR;
            cur.c = tempC;
            //이동한 파이어볼 저장
            map[cur.r][cur.c].add(cur);
        }
    }
    //파이어볼 분열 진행
    static void meteorFire(int N){
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                //파이어볼 개수가 2개 미만일 때
                if (map[r][c].size() < 2) {
                    map[r][c].clear();
                    continue;
                }

                //파이어볼 2개 이상일 때
                //질량합, 속력합, 홀수 개수, 짝수 개수
                int mSum = 0, sSum = 0, oddCount = 0, evenCount = 0;
                int size = map[r][c].size();
                //분열 진행!
                for (meteor cur : map[r][c]) {
                    mSum += cur.m;
                    sSum += cur.s;
                    if (cur.d % 2 == 1)    //방향 홀수일 때
                        oddCount++;
                    else        //방향 짝수일 때
                        evenCount++;
                    meteors.remove(cur);    //분열될 파이어볼 제거!
                }
                map[r][c].clear();
                mSum /= 5;    //분열될 질량 구하기
                if (mSum == 0)    //분열될 질량이 0이면 분열 실패!
                    continue;
                sSum /= size;    //분열될 속도 구하기
                //모든 파이어볼 방향이 짝수이거나 홀수일 때
                if (oddCount == size || evenCount == size) {
                    for (int i = 0; i < 8; i += 2)    //{0, 2, 4, 6} 방향 분열
                        meteors.add(new meteor(r, c, mSum, sSum, i));
                } else {
                    for (int i = 1; i < 8; i += 2)    //{1, 3, 5, 7} 방향 분열
                        meteors.add(new meteor(r, c, mSum, sSum, i));
                }
            }
        }
    }
    //파이어볼 질량의 합 구하는 함수
    static int meteorCal(){
        int result = 0;
        //모든 질량 더하기!
        for(meteor cur : meteors)
            result += cur.m;
        return result;
    }
}

 

해결 방법

1. K번 meteorMove(파이어볼 이동하는 메서드)와 meteorFire(파이어볼 분열하는 메서드)를 실행하여 모든 파이어볼 이동과 분열을 진행한다.
2. meteorCal을 실행하여 남은 파이어볼 질량의 합을 결과로 BufferedWriter에 저장한다.
3. BufferedWriter에 저장된 결과값을 출력한다.