코드 트리 - 마법의 숲 탐색(Java)

0. 개요

구현 문제입니다. 

 

이 문제를 해결하기 위해서 두 가지의 주의 사항이 있을거 같습니다.

1. 골렘의 시작점은 숲 밖이다.

2. 골렘 몸의 일부와 출구를 분리해야 한다.

 

1. 골렘의 시작점은 숲 밖이다.

아래와 같은 그림일 때, 어떻게 동작될까요?

 

정답은, 왼쪽으로 회전한다는 것입니다.

왼쪽으로 2회전이 가능하기 때문에 아래와 같은 그림으로 골렘의 이동이 종료됩니다.

 

이렇게 골렘은 숲 밖에서 부터 회전을 할 수 있습니다.

 

저는 이를 위해서 숲 바깥, 숲 위, 숲 안쪽을 각 -2, -1, 0 으로 표현했습니다.

이를 그림으로 표현하면 아래와 같습니다.

 

행과 열의 입력의 범위가 70 이하입니다.

저의 경우 편의상 80*80 배열을 만들어 (3,3) 부터 숲 내부가 되도록 고정시켰습니다.

 

좌측열에 패딩을 준 이유는

골렘 중앙을 기준으로 하, 좌, 우로 이동이 가능한지 판단하기 때문입니다.

 

골렘 중앙을 기준으로 두 칸 이내의 범위를 확인해야 하는데,

패딩을 줘야 ArrayOutOfBoundsException을 피할 수 있습니다.

 

2. 골렘 몸의 일부와 출구를 분리해야 한다.

저는 골렘의 일반 몸의 값을 홀수로 하고, 출구의 값을 짝수로 했습니다.

이렇게 한 이유는

BFS로 정령이 갈 수 있는 최대 행을 찾을 때, 짝수일 경우 다른 골렘으로 이동할 수 있게 하기 위함입니다.

 

이를 그림으로 표현하면 아래와 같습니다.

 

[구현 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static final int EMPTY = 0;
    private static final int TOP = -1;
    private static final int OUT_OF_RANGE = -2;

    // 네 방향 벡터
    private static final int[] DX = {-1, 0, 1, 0};
    private static final int[] DY = {0, 1, 0, -1};

    // 아래 이동 벡터
    private static final int[] DOWN_DX = {1, 2, 1};
    private static final int[] DOWN_DY = {-1, 0, 1};

    // 좌, 우 회전 벡터
    private static final int[] ROTATE_DX = {-1, 0, 1, 1, 2}; // 좌, 우 회전의 행 확인 범위는 같음
    private static final int[] LEFT_ROTATE_DY = {-1, -2, -1, -2, -1};
    private static final int[] RIGHT_ROTATE_DY = {1, 2, 1, 2, 1};

    private static final int[][] map = new int[80][80];

    private static int r, c, k, count = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz = new StringTokenizer(br.readLine());
        int answer = 0;

        r = Integer.parseInt(stz.nextToken());
        c = Integer.parseInt(stz.nextToken());
        k = Integer.parseInt(stz.nextToken());

        // 1. 마법의 숲 초기화
        initMap();

        while (k-- > 0) {
            stz = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(stz.nextToken()) + 2; // 3번 인덱스부터 쓰기 위해 2를 더함(입력은 1부터 주어짐)
            int d = Integer.parseInt(stz.nextToken());

            Node node = new Node(1, y, d); // 골렘 중앙 값

            // 조건에 의한 움직임이 멈출 때 까지 반복
            while (true) {
                if (canMoveDown(node)) { // 아래로 이동할 수 있는 경우
                    node.x += 1;
                } else if (canMoveLeftOrRight(node, Direction.LEFT)) { // 좌측 회전을 할 수 있는 경우
                    node.x += 1;
                    node.y -= 1;
                    node.d = (node.d == 0 ? DX.length - 1 : node.d - 1);
                } else if (canMoveLeftOrRight(node, Direction.RIGHT)) { // 우측 회전을 할 수 있는 경우
                    node.x += 1;
                    node.y += 1;
                    node.d = (node.d + 1) % DX.length;
                } else {
                    // 골렘이 숲 범위를 벗어 나면 초기화
                    if (node.x < 4 || node.y < 4 || node.x >= r + 3 || node.y >= c + 3) {
                        initForest();
                        break;
                    }

                    // 중간 좌표를 기준으로 골렘 공간 차지
                    map[node.x][node.y] = count;
                    for (int t = 0; t < DX.length; t++) {
                        int nx = node.x + DX[t];
                        int ny = node.y + DY[t];
                        if (isOutOfRange(nx, ny)) continue;

                        // 출구이면 짝수가 될 수 있도록 1 추가
                        map[nx][ny] = (t == node.d) ? count + 1 : count;
                    }

                    // 항상 출구를 제외한 위치는 홀수, 출구는 짝수 유지
                    count += 2;

                    answer += bfs(node);
                    break;
                }
            }
        }

        System.out.print(answer);
        br.close();
    }

    private static int bfs(Node node) {
        Queue<Node> qu = new LinkedList<>();
        qu.add(node);
        boolean[][] visited = new boolean[r + 4][c + 4];
        visited[node.x][node.y] = true;
        int max = node.x;

        while (!qu.isEmpty()) {
            Node cn = qu.poll();

            for (int t = 0; t < DX.length; t++) {
                int nx = cn.x + DX[t];
                int ny = cn.y + DY[t];

                if (isOutOfRange(nx, ny) || map[nx][ny] <= 0 || visited[nx][ny]) continue;

                // 같은 골렘이거나, 골렘의 출구이면 다른 골렘으로 이동 가능
                if (map[cn.x][cn.y] == map[nx][ny] ||
                        map[cn.x][cn.y] + 1 == map[nx][ny] ||
                        map[cn.x][cn.y] % 2 == 0) {
                    visited[nx][ny] = true;
                    qu.add(new Node(nx, ny, -1));

                    max = Math.max(max, nx); // 정령이 갈 수 있는 최대 위치 저장
                }
            }
        }

        //  상단의 길이 만큼 뺌(0번 인덱스 부터 시작하므로 3이 아닌 2를 빼야 함)
        return max - 2;
    }

    private static void initMap() {
        // 범위를 벗어나는지 초기화
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                map[i][j] = OUT_OF_RANGE;
            }
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 3; j < c + 3; j++) {
                map[i][j] = TOP;
            }
        }
        initForest();
    }

    // (3,3) 부터 유효 공간으로 사용
    private static void initForest() {
        for (int i = 3; i < r + 3; i++) {
            for (int j = 3; j < c + 3; j++) {
                map[i][j] = EMPTY;
            }
        }
    }

    // 밑으로 움직일 수 있는지 판단
    private static boolean canMoveDown(Node node) {
        for (int i = 0; i < DOWN_DX.length; i++) {
            int nx = node.x + DOWN_DX[i];
            int ny = node.y + DOWN_DY[i];

            // 범위를 벗어나거나 이전 골렘이 선점하고 있으면 false
            if (isOutOfRange(nx, ny) || map[nx][ny] > EMPTY) {
                return false;
            }
        }
        return true;
    }

    private static boolean canMoveLeftOrRight(Node node, Direction direction) {
        for (int i = 0; i < ROTATE_DX.length; i++) {
            int nx = node.x + ROTATE_DX[i];
            int ny = node.y + (direction == Direction.LEFT ? LEFT_ROTATE_DY[i] : RIGHT_ROTATE_DY[i]);

            // 범위를 벗어나거나 이전 골렘이 선점하고 있으면 false
            if (isOutOfRange(nx, ny) || map[nx][ny] > EMPTY) {
                return false;
            }
        }
        return true;
    }

    private static boolean isOutOfRange(int x, int y) {
        return map[x][y] == OUT_OF_RANGE;
    }

    private enum Direction {
        LEFT, RIGHT
    }

    private static class Node {
        int x, y, d;

        public Node(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
}