[BOJ] 20056. 마법사 상어와 파이어볼

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

접근 방법

구현 문제는 대부분 데이터를 어떻게 저장하는지에 따라 풀이가 달라진다. (제일 중요)

격자의 맵에서 데이터를 어떻게 담아줘야 할 지 생각을 했고

파이어볼2차 배열을 생각하였다.

LinkedList<Fire>[][] map = new LinkedList[N][N];
// 이렇게 할 경우 x,y에 대해 Fire 정보를 모두 가져올수 있기 때문이다.

또한, move를 해주게 될 때 map은 새로운 map이 되기 때문에 move를 해준 후 다시 추가를 해줘야한다.

static void move(){

        List<Fire> next[][] = new LinkedList[N][N];
        for(int i = 0; i < N; i++) {
            for (int k = 0; k < N; k++) {
                next[i][k] = new LinkedList<>();
            }
        }
        ... move end ...
        map = next;
}

주의사항

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결 ! 이 부분을 생각해야한다.

Need Know

1. 구현

전체 코드 ( Java )

import javax.swing.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

class Main{
    // 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int M;
    static int K;
    static List<Fire>[][] map;
    static int[] dx = {-1,-1,0,1,1,1,0,-1};
    static int[] dy = {0,1,1,1,0,-1,-1,-1};
    public static void main(String[] args) throws IOException {
        set();
        solve();
    }
    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = new LinkedList[N][N];
        for(int i = 0; i < N; i++) {
            for (int k = 0; k < N; k++) {
                map[i][k] = new LinkedList<>();
            }
        }
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            int m = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            map[x][y].add(new Fire(m,d,s));
        }
    }
    static void solve(){
        for(int i=0; i<K; i++){
            move();
        }
        int answer = 0;
        for(int i = 0; i < N; i++) {
            for(int k = 0; k < N; k++){
                for(Fire fire : map[i][k])
                    answer += fire.m;
            }
        }
        System.out.println(answer);
    }
    static void move(){

        List<Fire> next[][] = new LinkedList[N][N];
        for(int i = 0; i < N; i++) {
            for (int k = 0; k < N; k++) {
                next[i][k] = new LinkedList<>();
            }
        }
        for(int i=0; i<N; i++){
            for(int k=0; k<N; k++){
                if(map[i][k].size() > 0){
                    for(Fire fire : map[i][k]){
                        int dis = fire.s % N;
//                        System.out.println(i +" , " + k);
                        int nx = i + (dx[fire.d]*dis);
                        int ny = k + (dy[fire.d]*dis);
                        if(nx >= N) nx -= N;
                        else if(nx < 0) nx += N;
                        if(ny >= N) ny -= N;
                        else if(ny<0) ny += N;
//                        System.out.println(nx +" , " + ny + " ->"+fire.m);
                        next[nx][ny].add(new Fire(fire.m,fire.d,fire.s));
                    }
                }
            }
        }
        map = next;
        combine();
    }
    static void combine(){
        for(int i=0; i<N; i++){
            for(int k=0; k<N; k++){
                if(map[i][k].size() > 1){
                    int mSum = 0;
                    int sSum = 0;
                    boolean even = true, odd = true;
                    for(Fire fire : map[i][k]){
                        mSum += fire.m;
                        sSum += fire.s;
                        if(fire.d % 2 == 0){
                            odd = false;
                        }else{
                            even = false;
                        }
                    }
                    int newMSum = mSum / 5;
                    int newSSum = sSum / map[i][k].size();
                    map[i][k] = new LinkedList<>();

                    if(newMSum > 0){
                        for(int z=0; z<4; z++){
                            if(odd || even){
                                map[i][k].add(new Fire(newMSum, 2 * z, newSSum));
                            }else{
                                map[i][k].add(new Fire(newMSum, 1 + 2 * z, newSSum));
                            }
                        }
                    }
                }
            }
        }
    }
}
class Fire{
    int m,d,s; // 질량 방향 속력

    public Fire(int m, int d, int s) {
        this.m = m;
        this.d = d;
        this.s = s;
    }
}