[Codetree] 마법의 숲 탐색

https://www.codetree.ai/training-field/frequent-problems/problems/magical-forest-exploration/description

문제 이해

문제 자체는 시뮬레이션이므로 문제의 조건을 놓치지 않고 잘 따라가면 될 것이라 생각하며 풀었습니다.

접근 방법

골렘 이동
- 이미 숲의 최상단까지 골렘이 있어서 이번 골렘이 들어가지도 못하는 경우가 있을 수 있습니다. 저는 0행부터 사용하도록 구현했기 때문에 현재 골렘의 행 좌표가 -2일 떄와 -1일 때 맵 체크 조건을 다르게 하지 않으면 ArrayIndexOutOfBoundsException가 발생합니다. 이를 주의해야 했습니다.
- 왼쪽 또는 오른쪽으로 이동할 때 단순히 대각선으로 움직이는 것이 아니라 '왼쪽으로 한 칸 움직인 후 아래로 한 칸' 이동합니다. 그래서 대각선 아래의 두 칸만 확인하는 것이 아니라 최대 네 칸이 비어있는지 확인해야 합니다.
- 만약 골렘이 멈췄을 때 한 칸이라도 숲 밖에 있다면 모든 골렘을 지우고 점수도 얻지 못하는 것을 고려해야 합니다.
정령 이동
- 일반적인 맵 탐색 문제의 경우 모든 갈 수 있는 칸을 한 칸씩 이동하지만, 이 문제에서는 (1) 현재 골렘의 가장 남쪽 칸과 (2) 출구에서 갈 수 있는 다음 골렘만 찾으면 될거라고 생각했습니다.
탐색할 위치 좌표가 매우 많이 바뀌어야 하기 때문에 인덱스 수정에 주의가 필요합니다.

코드

public class Main {

    static int R, C, K, score, rMax;
    static int[][] m, gArr;
    static int[] di = {-1, 0, 1, 0}, dj = {0, 1, 0, -1};
    static boolean[] v;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        // initialise
        score = 0;
        initMap();
        gArr = new int[K][];
        

        // input K golems
        for (int k = 0; k < K; k++) {
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken()) - 1;
            int e = Integer.parseInt(st.nextToken());
            
            // init every try
            rMax = 0;
            v = new boolean[K];
            drop(k, -2, c, e);
        }
        System.out.println(score);
    }

    static void drop(int idx, int ci, int cj, int e) {
        while (true) {                  // move until available
            if (ci == R - 2) break;     // exit at bottom
            
            // go down
            if ((ci == -2 && m[ci + 2][cj] == -1) || (m[ci + 2][cj] == -1 && m[ci + 1][cj - 1] == -1 && m[ci + 1][cj + 1] == -1)) {
                ci += 1;
                continue;
            }

            // go left
            if (cj >= 2) {
                if ((ci == -2 && m[ci + 2][cj - 1] == -1) || ((ci == -1) && m[ci + 2][cj - 1] == -1 && m[ci + 1][cj - 1] == -1 && m[ci + 1][cj - 2] == -1) || (m[ci + 2][cj - 1] == -1 && m[ci + 1][cj - 1] == -1 && m[ci + 1][cj - 2] == -1 && m[ci][cj - 2] == -1)) {
                    ci += 1;
                    cj -= 1;
                    e = (e + 3) % 4;
                    continue;
                }
            }

            // go right
            if (cj < C - 2) {
                if ((ci == -2 && m[ci + 2][cj + 1] == -1) || ((ci == -1) && m[ci + 2][cj + 1] == -1 && m[ci + 1][cj + 1] == -1 && m[ci + 1][cj + 2] == -1) || (m[ci + 2][cj + 1] == -1 && m[ci + 1][cj + 1] == -1 && m[ci + 1][cj + 2] == -1 && m[ci][cj + 2] == -1)) {
                    ci += 1;
                    cj += 1;
                    e = (e + 1) % 4;
                    continue;
                }
            }

            // exit when cannot go anymore
            break;
        }

        // reset if golem located outside of the map
        if (ci <= 0) {
            initMap();
            return;
        }

        // mark golem on map
        m[ci][cj] = m[ci - 1][cj] = m[ci][cj + 1] = m[ci + 1][cj] = m[ci][cj - 1] = idx;
        gArr[idx] = new int[] {ci, cj, e};

        moveGolem(idx);
        score += rMax;
    }
 
    static void moveGolem(int idx) {
        v[idx] = true; // visited

        // update rMax with the bottom of current golem
        int ri = gArr[idx][0] + 2;
        rMax = ri > rMax ? ri : rMax;

        // exit coord of current golem
        int e = gArr[idx][2];
        ri = gArr[idx][0] + di[e];
        int rj = gArr[idx][1] + dj[e];

        // find next golem close to current colem's exit
        for (int d = 0; d < 4; d++) {
            int ni = ri + di[d];
            int nj = rj + dj[d];

            if (ni < 0 || ni >= R || nj < 0 || nj >= C) continue;
            if (m[ni][nj] == -1 || v[m[ni][nj]]) continue;

            moveGolem(m[ni][nj]);
        }
    }

    static void initMap() {
        m = new int[R][];
        for (int r = 0; r < R; r++) {
            m[r] = new int[C];
            Arrays.fill(m[r], -1);
        }
    }
}