[JAVA] 백준 마법사 상어와 파이어볼

이틀만에 성공했다...

 

grid는 x,y를 row col을 이처럼 적용해야된다.

 

보통 (r,c)로 주어지니 (y,x)로 받아야한다!!

(r,c)로 주어지면 (y,x)로 받아야함.

 

우선 아래 코드에서는 x,y값을 반대로 적용했다.

r,c 를 x,y에 받으면 생기는 일

그래서 문제 푸는내내 계속 헷갈렸다.

 

 

가장 큰 실수는 

잘못된 부분은 아래에 정리하겠다.

import java.util.*;

class Main {
    public static int N, M, K;
    public static ArrayList<ArrayList<Queue<Fireball>>> fireball;
    public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    public static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
        fireball = new ArrayList<>();
        for (int i = 0; i <= N; i++) {//0~N
            fireball.add(new ArrayList<>());
            for (int j = 0; j <= N; j++) fireball.get(i).add(new LinkedList<>());//0~N
        }
        for (int i = 0; i < M; i++) {
            int r = sc.nextInt();
            int c = sc.nextInt();
            int m = sc.nextInt();
            int s = sc.nextInt();
            int d = sc.nextInt();
            fireball.get(r).get(c).offer(new Fireball(m, s, d));
        }
        //input끝
        for (int k = 0; k < K; k++) {
            //System.out.println("kkkkkkkkkk" + k);
            move(k);//이동
            // System.out.println("split");
            sumSplit(k);
        }

        System.out.println(print());
    }

    static int print() {
        int sum = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                while (!fireball.get(i).get(j).isEmpty()) {
                    Fireball b = fireball.get(i).get(j).poll();
                    sum += b.m;
                    //System.out.println("안뽀개진거:"+i+","+j);
                }
            }
        }
        return sum;
    }

    static class Fireball {
        int m, s, d;
        int kcount = 0;

        Fireball(int m, int s, int d) {
            this.m = m;//질량
            this.s = s;//몇칸이동
            this.d = d;//방향
        }

        Fireball(int m, int s, int d, int k) {
            this.kcount = k;
            this.m = m;//질량
            this.s = s;//몇칸이동
            this.d = d;//방향
        }
    }

    static void move(int k) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (fireball.get(i).get(j).isEmpty()) continue;
                int size = fireball.get(i).get(j).size();
                for (int s = 0; s < size; s++) {
                    Fireball b = fireball.get(i).get(j).poll();
                    if (b.kcount > k) {
                        fireball.get(i).get(j).offer(b);
                        continue;//이미 k번째
                    } else {//현위치 i,j
                        //System.out.print("(" + i + "," + j + ")");
                        b.kcount += 1;
                        int x = i + ((b.s % N) * dx[b.d]);
                        int y = j + ((b.s % N) * dy[b.d]);

                        if (x > 1) x = x % N;//업오버플로우
                        if (x < 1) x = N - Math.abs(x);//다운오버플로우

                        if (y > 1) y = y % N;//업오버플로우
                        if (y < 1)
                            y = N - Math.abs(y);//다운오버플로우

                        fireball.get(x).get(y).offer(b);

                        //System.out.println("->(" + x + "," + y + ")"+b.d);
                    }
                }
            }
        }
    }

    static void sumSplit(int k) {
        ++k;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                int size = fireball.get(i).get(j).size();
                if (size >= 2) {//2이상이면 합쳐
                    int split_m = 0, split_s = 0, split_d = 0;
                    for (int sz = 0; sz < size; sz++) {
                        Fireball b = fireball.get(i).get(j).poll();
                        split_m += b.m;
                        split_d += b.d % 2;
                        split_s += b.s;
                    }
                    split_m = split_m / 5;
                    if (split_m == 0) {
                        //System.out.println("뽀각");
                        continue;
                    }
                    //질량0이면 패스------------
                    split_s = split_s / size;
                    //System.out.println("s:" + split_s);
                    if (split_d == size || split_d == 0) {//모두 홀수(2n+2k+2l)+size거나 짝수 0246
                        fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 0, k));
                        fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 2, k));
                        fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 4, k));
                        fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 6, k));
                    } else {//1357
                        fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 1, k));
                        fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 3, k));
                        fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 5, k));
                        fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 7, k));
                    }
                }
            }
        }
    }
}

하이라이트부분.

1~N을 초과/미만인 좌표는 서로 연결된다.

즉, 그리드 인덱스 오버플로우시 0=>N으로, N+1=>1로 바꿔주라는 뜻이다.

 

이 부분에서 mod연산을 하는 와중 실수가 계속되었다.

해결에 도움을 준 질문/답변자에게 감사의 링크를 남긴다.(www.acmicpc.net/board/view/66407)

int x = i + ((b.s % N) * dx[b.d]);
int y = j + ((b.s % N) * dy[b.d]);

f (x > 1) x = x % N;//업오버플로우
if (x < 1) x = N - Math.abs(x);//다운오버플로우

if (y > 1) y = y % N;//업오버플로우
if (y < 1) y = N - Math.abs(y);//다운오버플로우

fireball.get(x).get(y).offer(b);

나는 내가 mod연산을 잘 했다고 생각했는데, 다른방식으로 다시 연산하니 성공하였다.

아마 계산해보지 못한 경우의 수가 남아있던 것 같다.

 

두가지 추가 테스트케이스를 남겨두겠다.

4 6 4
1 1 5 1 1
3 3 5 1 5
1 3 5 1 3
3 1 5 1 7
2 2 5 1 3
3 2 5 1 2

-> 4

 

4 9 5
3 2 8 5 2
3 3 19 3 4
3 1 7 1 1
4 4 6 4 0
2 1 6 2 5
4 3 9 4 3
2 2 16 1 2
4 2 17 5 3
3 4 3 5 7

-> 33