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

📌 난이도

🥇 Gold 4

📌 문제

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

📌 풀이

와… 2번째로 도전하는 골드4 문제와 동시에 처음으로 푼 골드 4 문제이다.
밥먹는 시간 제외하고, 8시간은 꼬박 이 문제만 풀은 것 같다.
그나마 쉽게 풀린 이유는 메모리 제한이 널널하고, 칸의 넓이가 50밖에 안되서 50^4 = 6250000이라는 o(n^4)가 나와도 걱정없는 문제라서 메모리 걱정안하고 풀어서 쉽게 해결된 문제인것 같다.

처음에는 N x N크기의 pos라는 클래스를 인자로 가지는 2차원 배열을 사용하여 구상을 하였다.
파이어볼이라는 객체를 여러개 구현하는 형식이 아닌, 각 주소값에 현재 파이어볼의 정보를 저장시키는 방식으로 구상을 하였다.
이중 for문을 사용하여, BFS처럼 첫칸부터 마지막 칸까지 순서대로 이동시키는 식으로 구현을 하려고 하였다.
이를 위하여 속도 * DR[i] + 현재위치를 이용하여 다음 칸의 위치를 구하려고 했는데, 이 위치가 N보다 작을수도, 클수도 있다는 문제점이 있었다.
이를 해결하기 위하여, cur[0] + ((ODR[j] * curs+ N) % N처럼 일부러 N을 더해서 양수로 만들고 N으로 나눠서 인덱스 문제를 해결하려고 하였다.
하지만 만들고보니 속도가 너무커서 N을 더해준값보다 더 클 수도 있다는 생각이 들었다.
그래서 속도를 N으로 나눈 나머지에 N값을 더해주고 다시 %N연산을 해주는 살짝은 번거로운 다음과 같은 연산을 이용하여 구현하였다.

(cur[0] + ((ODR[j] * curs) % N + N)) % N

이후 코드를 작성하다가 visited 배열을 사용하더라도 해결이 안되는 문제가 하나 있었는데 바로, 파이어볼이 다음과 같이 파이어볼1이 [2,2]의 위치로 이동하려고 할떄 하필 그자리에 다른 파이어볼이 있으면, 파이어볼1은 두번 이동하게 되게 된다.

이를 해결하기 위하여 파이어볼1이 이동한 후, [2,2]의 자리를 visited 배열에 넣어서, 검사를 안하면 파이어볼2는 움직이지 않게 된다.

이를 해결하기 위하여 결국 다음상태와 현재상태를 구별해야 된다는 것을 느끼고, 코드를 처음부터 다시 짜기 시작했다.
메모리양이 넉넉하다는 것을 이용해 그냥 currentfield 와 field 를 만들어서 현재 상태와 다음 상태를 구별하였다.
그리고, 폭발을 어떻게 구현해야 하나 순서를 고민하다가, 항상 폭발 -> 이동 방식으로 isExplode라는 변수를 추가하여, 이동하기전에 isExplode가 거짓이면 그대로, 참이면 각각 EDR, ECR, ODR, OCR이라는 상수 인트 배열을 만들어서 dir % 8 값이 짝수면 앞의 두개, 홀수면 뒤에 두개를 사용하여 폭발을 구현하였다.
하지만 여기서 크나큰 오차가 하나 생기는데 뒤에서 설명하겠다.

이후, 합치는 것을 계속 구현하다가 속도 부분에서 문제가 생겼다.
원래 기존 들어온 값에 새값을 더해서 2를 나누는 식으로 구현을 하려다가, 자세히 계산을 해보니, count라는 변수값이 무조건 필요하다는 것을 알게되었다.
그래서 뒤늦게 pos에 넣어주었다.

하지만 이 모든 오류를 고치고 나서도 계속 1%에서 틀리는 상황이 반복되었다.
너무나도 화가났지만 차분하게 디버깅을 찍으면서 한가지 문제점을 알게 되었다.
문제에서 모두 짝수이거나, 홀수일때 조건에서 짝 + 짝 % 2 == 홀 + 홀 % 2 == 0 의 개념으로 접근을 했는데, 짝 짝 홀 홀 같은경우 처리가 제대로 되지 않는 것이였다.
뒤늦게 이 사실을 깨닫고 고치기 위해서 isSame이라는 변수를 넣고 final 상수를 사용하여 이것을 class 내부에서 구별을 하게 구현하였다.

너무 어려웠고, 시간이 오래걸렸지만, 풀어내니까 행복했다. 😎

📌 Code

package BOJ.Implements;

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

public class N20056 {
    static class pos {
        int m;
        int s;
        int d;
        boolean isExplode;
        int count;
        int isSame;

        public pos(int m, int s, int d, int count, int isSame, boolean isExplode) {
            this.m = m;
            this.s = s;
            this.d = d;
            this.count = count;
            this.isSame = isSame;
            this.isExplode = isExplode;
        }

        public boolean BigBang(int m, int s, int d) {
            if (this.m != 0) {
                this.isExplode = true;
                this.count += 1;
                if (this.isSame == notSame) {
                    this.isSame = notSame;
                } else if ((this.isSame == empty) || (this.isSame == d % 2)) {
                    this.isSame = d % 2;
                } else {
                    this.isSame = notSame;
                }
            } else {
                this.isSame = d % 2;
                this.isExplode = false;
                this.count = 1;
            }
            this.m += m;
            this.s += s;
            this.d += d;
            this.d %= 8;
            return isExplode;
        }

        public void reset() {
            this.m = 0;
            this.s = 0;
            this.d = 0;
            this.count = 0;
            this.isSame = empty;
            this.isExplode = false;
        }
    }


    static pos[][] field;
    static pos[][] curfield;
    static Queue<Integer[]> fire;
    static int N;
    static int M;
    static int K;
    static int empty = -1;
    static int notSame = -2;
    static final int[] DR = {-1, -1, 0, 1, 1, 1, 0, -1};
    static final int[] DC = {0, 1, 1, 1, 0, -1, -1, -1};
    static final int[] EDR = {-1, 0, 1, 0};
    static final int[] EDC = {0, 1, 0, -1};
    static final int[] ODR = {-1, 1, 1, -1};
    static final int[] ODC = {1, 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());

        curfield = new pos[N][N];
        field = new pos[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                field[i][j] = new pos(0, 0, 0, 1, empty, false);
                curfield[i][j] = new pos(0, 0, 0, 1, empty, false);
            }
        }
        fire = new LinkedList<>();
        int r;
        int c;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken()) - 1;
            c = Integer.parseInt(st.nextToken()) - 1;
            field[r][c] = new pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 1, empty, false);
            fire.add(new Integer[]{r, c});
        }
        TotalTime(K);
    }

    static void TotalTime(int time) {
        //ShowAll();
        for (int i = 0; i < time; i++) {
            MoveFire();
            //ShowAll();
        }
        Count();
    }

    static void MoveFire() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                curfield[i][j] = new pos(field[i][j].m, field[i][j].s, field[i][j].d, field[i][j].count, field[i][j].isSame, field[i][j].isExplode);
                field[i][j].reset();
            }
        }
        int count = fire.size();
        int nextR;
        int nextC;
        int curm;
        int curs;
        int curd;
        Integer[] cur;
        for (int i = 0; i < count; i++) {
            cur = fire.poll();
            curm = curfield[cur[0]][cur[1]].m;
            curs = curfield[cur[0]][cur[1]].s;
            curd = curfield[cur[0]][cur[1]].d;
            if (curm <= 0) {
                continue;
            }
            if (!curfield[cur[0]][cur[1]].isExplode) {
                nextR = (cur[0] + ((DR[curd] * curs) % N + N)) % N;
                nextC = (cur[1] + ((DC[curd] * curs) % N + N)) % N;
                if (!field[nextR][nextC].BigBang(curm, curs, curd)) {
                    fire.add(new Integer[]{nextR, nextC});
                }
            } else {
                curm /= 5;
                curs /= curfield[cur[0]][cur[1]].count;
                if (curm <= 0) {
                    continue;
                }
                if (curfield[cur[0]][cur[1]].isSame == notSame) {
                    for (int j = 0; j < ODC.length; j++) {
                        nextR = (cur[0] + ((ODR[j] * curs) % N + N)) % N;
                        nextC = (cur[1] + ((ODC[j] * curs) % N + N)) % N;
                        if (!field[nextR][nextC].BigBang(curm, curs, 2 * j + 1)) {
                            fire.add(new Integer[]{nextR, nextC});
                        }
                    }
                } else {
                    for (int j = 0; j < EDC.length; j++) {
                        nextR = (cur[0] + ((EDR[j] * curs) % N + N)) % N;
                        nextC = (cur[1] + ((EDC[j] * curs) % N + N)) % N;
                        if (!field[nextR][nextC].BigBang(curm, curs, 2 * j)) {
                            fire.add(new Integer[]{nextR, nextC});
                        }
                    }
                }
            }
        }
    }

    static void Count() {
        int result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (field[i][j].isExplode) {
                    result += (field[i][j].m / 5) * 4;
                } else {
                    result += field[i][j].m;
                }
            }
        }
        System.out.println(result);
    }


    static void ShowAll() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (field[i][j].m == 0) {
                    System.out.print(". ");
                } else if (field[i][j].isExplode) {
                    System.out.print(field[i][j].m + ")");
                } else {
                    System.out.print(field[i][j].m + " ");
                }
            }
            System.out.println();
        }
        System.out.println("==========================");
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

📌 추가 예제

[Input]
7 4 5
1 1 1 1 3
1 3 2 1 5
3 1 3 1 1
3 3 4 1 7

[Output]
8

[Input]
7 4 5
1 2 1 1 4
2 3 2 1 6
3 1 3 1 1
3 3 4 1 7

[Output]
8

[Input]
7 1 10
4 4 7 1 7

[Output]
7

[Input]
7 0 10

[Output]
0

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁