[코드트리 챌린지] 메이즈 러너

문제 : 메이즈 러너

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

삼성 코딩테스트 대비 기출이라 참고하는 용도 정도로 글을 보면 좋으리라 생각됩니다.

 

코드는 아래와 같습니다.

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;

    static int n, m, k, moveCnt;
    static int[][] maze;
    static Pos exit;
    static final int[] dy = {-1, 1, 0, 0};
    static final int[] dx = {0, 0, -1, 1};

    static boolean humanExist;

    static void input() throws Exception {

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        maze = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                maze[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            maze[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1]--;
        }
        st = new StringTokenizer(br.readLine());
        exit = new Pos(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1, Integer.MIN_VALUE);
        maze[exit.y][exit.x] = -101;
    }

    static void moveHuman() {

        ArrayList<Pos> humanList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (maze[i][j] < 0) {
                    if (maze[i][j] == -101) continue;
                    humanList.add(new Pos(i, j, maze[i][j]));
                    maze[i][j] = 0;
                }
            }
        }

        for (Pos human : humanList) {
            int curDist = human.calDistFromExit(human.y, human.x);
            humanExist = true;
            for (int i = 0; i < 4; i++) {
                int ny = human.y + dy[i];
                int nx = human.x + dx[i];
                if (ny == -1 || nx == -1 || ny == n || nx == n) continue;
                if (maze[ny][nx] > 0) continue;
                if (curDist <= human.calDistFromExit(ny, nx)) continue;

                moveCnt -= human.people;
                if (maze[ny][nx] != -101) {
                    maze[ny][nx] += human.people;
                }
                human.people = Integer.MIN_VALUE;
                break;
            }
        }

        for (Pos human : humanList) {
            if (human.people == Integer.MIN_VALUE) continue;
            maze[human.y][human.x] += human.people;
        }

    }

    static void rotateMaze() {
        for (int squareSize = 1; squareSize < n; squareSize++) {

            boolean canRotate = false;
            int squareLeftTopY = exit.y - squareSize;
            int squareLeftTopX = exit.x - squareSize;
            for (int leftTopY = squareLeftTopY; leftTopY <= exit.y; leftTopY++) {

                for (int leftTopX = squareLeftTopX; leftTopX <= exit.x; leftTopX++) {
                    int rightBottomY = leftTopY + squareSize;
                    int rightBottomX = leftTopX + squareSize;
                    if (leftTopY < 0 || leftTopX < 0 || rightBottomY >= n || rightBottomX >= n) continue;

                    for (int y = leftTopY; y <= rightBottomY; y++) {
                        for (int x = leftTopX; x <= rightBottomX; x++) {
                            if (maze[y][x] < 0 && maze[y][x] != -101) {
                                canRotate = true;
                                break;
                            }
                        }
                        if (canRotate) break;
                    }

                    if (canRotate) {
                        rotate(squareSize + 1, leftTopY, leftTopX, rightBottomY, rightBottomX);
                        break;
                    }
                }
                if (canRotate) break;
            }
            if (canRotate) break;
        }
    }

    static void rotate(int size, int startY, int startX, int endY, int endX) {

        int[][] prevMaze = new int[size][size];

        for (int i = startY; i <= endY; i++) {
            for (int j = startX; j <= endX; j++) {
                prevMaze[i - startY][j - startX] = maze[i][j];
            }
        }

        int[][] nextMaze = new int[size][size];

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                nextMaze[j][size - i - 1] = prevMaze[i][j];
                if (nextMaze[j][size - i - 1] > 0) nextMaze[j][size - i - 1]--;
            }
        }

        for (int i = startY; i <= endY; i++) {
            for (int j = startX; j <= endX; j++) {
                maze[i][j] = nextMaze[i - startY][j - startX];
                if (maze[i][j] == -101) {
                    exit = new Pos(i, j, Integer.MIN_VALUE);
                }
            }
        }
    }

    static void pro() {
        while (k-- > 0) {
            humanExist = false;
            moveHuman();
            if (!humanExist) break;
            rotateMaze();
        }
        sb.append(moveCnt).append('\n');
        sb.append(exit.y + 1).append(' ').append(exit.x + 1);
        System.out.println(sb);
    }

    static class Pos{
        int y, x, people;
        Pos(int _y, int _x, int _people) {
            y = _y; x = _x; people = _people;
        }

        int calDistFromExit(int ny, int nx) {
            return Math.abs(nx - exit.x) + Math.abs(ny - exit.y);
        }
    }
    public static void main(String[] args) throws Exception{
        input();
        pro();
    }


}

2차원 배열 돌리는 아이디어를 적용하기가 어려웠던 문제였고,

최근 삼성 코딩테스트에 비해 난이도가 상대적으로 쉬웠다는 평가를 받고 있던데 열심히 해야겠다는 생각이 들었다..