[Codetree] 마법의 숲 탐색

2024 상반기 오후 1번

순수 시간 5시간 소요

 

설계에 많은 시간을 투자했던 문제이다

 

이전에 "왕실의 기사 대결" 문제 설계할 때처럼 골렘 객체 2차원 배열을 만들까 고민했는데,

십자 범위로 골렘의 위치를 표기하는 배열과, 골렘의 상태를 저장하는 1차원 배열로 해결했다.

 

2차원 테트리스 구현하듯이 한칸씩 내려가면서, 다음 칸에 갈 수 있는지 조건 잘 걸어주면 골렘은 잘 쌓였다

 

근데 그 다음에 골렘 위에 탄 정령이 이동하는 로직에서 함수를 쪼개고, 디버깅하느라 여기서 시간을 좀 많이 썼다.

 

빨리 풀려면 초반부 골렘 내려오는 곳을 굉장히 빠르게 짰으면 더 빠르게 끝났을듯.. ?

 

디버깅 포인트

1. visited 배열 초기화 하는 위치 잘 선정

2. 좌표가 범위를 벗어나지 않는지 체킹하는 함수 꼭 따로 빼자

return row >= 3 && row < R + 3 && column >= 0 && column < C && board[row][column] != 0;

3. 변수명 잘 보기.. 현재 골렘 위치와 directions 배열 돌리는 골렘 위치 변수 헷갈려서 30분 날렸다.

4. 수도코드 잘 짜는 것은 항상 도움이 된다. 이번에 수도 코드 잘 짜서 구현 혼자 잘 한듯

제출 코드

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

public class Main {
    private static int R;
    private static int C;
    private static int K;
    private static Golem[] golemStatus;
    private static int[][] board;
    private static boolean[][] visited;
    private static int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public static void main(String[] args) throws IOException{
        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());

        // 초기 위치 고려 상위 3행 더
        board = new int[R+3][C];
        visited = new boolean[R+3][C];
        golemStatus = new Golem[K+1];

        int answer = 0;

        for(int golemNumber = 1; golemNumber <= K; golemNumber++) {
            st = new StringTokenizer(br.readLine());
            int initColumn = Integer.parseInt(st.nextToken());
            int wayOut = Integer.parseInt(st.nextToken());

            setGolemOnBoard(golemNumber, initColumn - 1);
            golemStatus[golemNumber] = new Golem(1, initColumn - 1, wayOut);

            // print();
            answer += execute(golemNumber);            
            // print();
        }

        System.out.println(answer);
    }

    private static int execute(int golemNumber) {
        while(true) {
            if(canMoveSouth(golemNumber)) {
                moveSouth(golemNumber);
                continue;
            } else if(canMoveWest(golemNumber)) {
                moveWest(golemNumber);
                continue;
            } else if(canMoveEast(golemNumber)) {
                moveEast(golemNumber);
                continue;
            }
            break;
        }

        // print();

        if(!checkGolemOutOfBoard(golemNumber)) {
            // 골렘이 숲 밖이면 점수합산 X
            clearBoard();
            return 0;
        }

        int result = moveJungryoungToBottom(golemNumber);
        return result;
    }

    private static void clearBoard() {
        for(int i = 0; i < board.length; i++) {
            Arrays.fill(board[i], 0);
        }
    }

    private static boolean checkGolemOutOfBoard(int golemNumber) {
        int centerRow = golemStatus[golemNumber].row;
        int centerColumn = golemStatus[golemNumber].column;
        // System.out.println(golemNumber + "번 골렘의 중앙값: " + centerRow + ", "  +centerColumn);

        for(int i = 0; i < directions.length; i++) {
            int nr = centerRow + directions[i][0];
            int nc = centerColumn + directions[i][1];
            if(!isValidPoint(nr, nc)) {
                // System.out.println("GOLEM OUT: " + nr + ", " + nc);
                return false;
            }
        }
        return true;
    }

    private static boolean isValidPoint(int row, int column) {
        return row >= 3 && row < R + 3 && column >= 0 && column < C && board[row][column] != 0;
    }

    private static int moveJungryoungToBottom(int golemNumber) {
        visited = new boolean[R+3][C];

        // System.out.println("MOVE JUNGRYUNG");
        int centerRow = golemStatus[golemNumber].row;
        int centerColumn = golemStatus[golemNumber].column;

        Queue<int[]> queue = new LinkedList<>();
        // 시작
        queue.offer(new int[]{centerRow, centerColumn});

        // System.out.println(golemNumber + "번 골렘 출구: " + (golemStatus[golemNumber].row + directions[golemStatus[golemNumber].wayOut][0]) + ", " + (
        // golemStatus[golemNumber].column + directions[golemStatus[golemNumber].wayOut][1]));

        int maxRow = 0;
        while(!queue.isEmpty()) {
            // 뽑고
            int[] current = queue.poll();
            // 방문 처리
            visited[current[0]][current[1]] = true;
            // System.out.print("[" + current[0] + ", " + current[1] + "] ");
            // 최대 행값 갱신
            maxRow = Math.max(maxRow, current[0] - 2);
            
            // 현재 칸의 골렘 넘버를 찾는다
            int currentGolemNumber = board[current[0]][current[1]];

            // 동서남북 점검
            for(int i = 0; i < directions.length; i++) {
                int nr = current[0] + directions[i][0];
                int nc = current[1] + directions[i][1];

                int nWayOut = golemStatus[currentGolemNumber].wayOut;
                // System.out.println("CURRENT: " + current[0] + ", " + current[1]);
                if(isValidPoint(nr, nc) && !visited[nr][nc]) { // 다음칸이 0이 아니고 보드를 벗어나지 않고며, 방문하지 않은 경우만 
                    if(board[nr][nc] == currentGolemNumber) { // 같은 골렘 내부
                        queue.offer(new int[]{nr, nc});
                        visited[nr][nc] = true;
                    } else if(
                        current[0] == golemStatus[currentGolemNumber].row + directions[nWayOut][0] &&
                        current[1] == golemStatus[currentGolemNumber].column + directions[nWayOut][1]
                    ) { // 다음칸이 같은 골렘 내부가 아니면 현재 위치가 출구일 경우에만 
                        queue.offer(new int[]{nr, nc});
                        visited[nr][nc] = true;
                    }
                    // 그런것도 아니라면 추가 X
                }
            }
        }
        // System.out.println();
        // System.out.println("적립: " + maxRow);
        return maxRow;
    }

    private static void moveSouth(int golemNumber) {
        // System.out.println("MOVE SOUTH");
        int centerRow = golemStatus[golemNumber].row;
        int centerColumn = golemStatus[golemNumber].column;

        // 기존 골렘 위치 삭제
        board[centerRow][centerColumn] = 0;
        for(int i = 0; i < directions.length; i++) {
            board[centerRow + directions[i][0]][centerColumn + directions[i][1]] = 0;
        }

        // 새 위치
        board[centerRow + 1][centerColumn] = golemNumber;
        for(int i = 0; i < directions.length; i++) {
            board[centerRow + 1 + directions[i][0]][centerColumn + directions[i][1]] = golemNumber;
        }

        // 새 위치 반영
        golemStatus[golemNumber].row = centerRow + 1;
    }

    private static void moveWest(int golemNumber) {
        // System.out.println("MOVE WEST");
        int centerRow = golemStatus[golemNumber].row;
        int centerColumn = golemStatus[golemNumber].column;

        // 기존 골렘 위치 삭제
        board[centerRow][centerColumn] = 0;
        for(int i = 0; i < directions.length; i++) {
            board[centerRow + directions[i][0]][centerColumn + directions[i][1]] = 0;
        }

        // 새 위치
        board[centerRow + 1][centerColumn - 1] = golemNumber;
        for(int i = 0; i < directions.length; i++) {
            board[centerRow+ 1 + directions[i][0]][centerColumn - 1 + directions[i][1]] = golemNumber;
        }
        
        // 새 위치 반영
        golemStatus[golemNumber].row = centerRow + 1;
        golemStatus[golemNumber].column = centerColumn - 1;

        // 출구 반시계방향으로 이동
        int wayOutResult = golemStatus[golemNumber].wayOut - 1;
        golemStatus[golemNumber].wayOut = wayOutResult < 0 ? 3 : wayOutResult;
    }

    private static void moveEast(int golemNumber) {
        // System.out.println("MOVE EAST");
        int centerRow = golemStatus[golemNumber].row;
        int centerColumn = golemStatus[golemNumber].column;

        // 기존 골렘 위치 삭제
        board[centerRow][centerColumn] = 0;
        for(int i = 0; i < directions.length; i++) {
            // System.out.println((centerRow + directions[i][0]) + ", " + (centerColumn + directions[i][1]));

            board[centerRow + directions[i][0]][centerColumn + directions[i][1]] = 0;
        }

        // 새 위치
        board[centerRow + 1][centerColumn + 1] = golemNumber;
        for(int i = 0; i < directions.length; i++) {
            // System.out.println((centerRow + 1 + directions[i][0]) + ", " + (centerColumn + 1 + directions[i][1]));

            board[centerRow + 1 + directions[i][0]][centerColumn + 1 + directions[i][1]] = golemNumber;
        }

        // 새 위치 반영
        golemStatus[golemNumber].row = centerRow + 1;
        golemStatus[golemNumber].column = centerColumn + 1;

        // 출구 시계방향으로 이동
        int wayOutResult = golemStatus[golemNumber].wayOut + 1;
        golemStatus[golemNumber].wayOut = wayOutResult > 3 ? 0 : wayOutResult;
    }

    private static boolean canMoveSouth(int golemNumber) {
        int centerRow = golemStatus[golemNumber].row;
        int centerColumn = golemStatus[golemNumber].column;
        
        // 골렘의 중앙(정령)이 보드 R - 2행에 왔으면
        if(centerRow >= R + 1) return false;

        if(board[centerRow + 1][centerColumn - 1] != 0) return false;
        if(board[centerRow + 2][centerColumn] != 0) return false;
        if(board[centerRow + 1][centerColumn + 1] != 0) return false;

        return true;
    }

    private static boolean canMoveWest(int golemNumber) {
        int centerRow = golemStatus[golemNumber].row;
        int centerColumn = golemStatus[golemNumber].column;
        
        // 골렘의 중앙(정령)이 보드 R - 2행에 왔으면
        if(centerRow >= R + 1) return false;
        // 골렘의 중앙(정령)이 보드 1열에 왔으면
        if(centerColumn <= 1) return false;

        // 남쪽 점검
        if(board[centerRow - 1][centerColumn - 1] != 0) return false;
        if(board[centerRow][centerColumn - 2] != 0) return false;
        if(board[centerRow + 1][centerColumn - 1] != 0) return false;

        // 서쪽 점검
        if(board[centerRow + 1][centerColumn - 2] != 0) return false;
        if(board[centerRow + 2][centerColumn - 1] != 0) return false;

        return true;
    }

    private static boolean canMoveEast(int golemNumber) {
        int centerRow = golemStatus[golemNumber].row;
        int centerColumn = golemStatus[golemNumber].column;
        
        // 골렘의 중앙(정령)이 보드 R - 2행에 왔으면
        if(centerRow >= R + 1) return false;
        // 골렘의 중앙(정령)이 보드 C - 2행에 왔으면
        if(centerColumn >= C - 2) return false;

        // 남쪽 점검
        if(board[centerRow - 1][centerColumn + 1] != 0) return false;
        if(board[centerRow][centerColumn + 2] != 0) return false;
        if(board[centerRow + 1][centerColumn + 1] != 0) return false;

        // 동쪽 점검
        if(board[centerRow + 2][centerColumn + 1] != 0) return false;
        if(board[centerRow + 1][centerColumn + 2] != 0) return false;

        return true;
    }

    private static void setGolemOnBoard(int golemNumber, int initColumn) {
        board[1][initColumn] = golemNumber;
        for(int i = 0; i < directions.length; i++) {
            board[1 + directions[i][0]][initColumn + directions[i][1]] = golemNumber;
        }
    }

    private static void print() {
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

class Golem {
    int row, column;
    int wayOut;

    public Golem(int row, int column, int wayOut) {
        this.row = row;
        this.column = column;
        this.wayOut = wayOut;
    }
}

 

정답 코드

음 삼성 기출 풀때 느끼는 거지만 정답 코드처럼은 절대 못 짤듯

너무 깔끔하네요..

import java.util.*;

public class Main {
    private static final int MAX_L = 70;

    private static int R, C, K; // 행, 열, 골렘의 개수를 의미합니다
    private static int[][] A = new int[MAX_L + 3][MAX_L]; // 실제 숲을 [3~R+2][0~C-1]로 사용하기위해 행은 3만큼의 크기를 더 갖습니다
    private static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1};
    private static boolean[][] isExit = new boolean[MAX_L + 3][MAX_L]; // 해당 칸이 골렘의 출구인지 저장합니다
    private static int answer = 0; // 각 정령들이 도달할 수 있는 최하단 행의 총합을 저장합니다

    // (y, x)가 숲의 범위 안에 있는지 확인하는 함수입니다
    private static boolean inRange(int y, int x) {
        return 3 <= y && y < R + 3 && 0 <= x && x < C;
    }

    // 숲에 있는 골렘들이 모두 빠져나갑니다
    private static void resetMap() {
        for (int i = 0; i < R + 3; i++) {
            for (int j = 0; j < C; j++) {
                A[i][j] = 0;
                isExit[i][j] = false;
            }
        }
    }

    // 골렘의 중심이 y, x에 위치할 수 있는지 확인합니다.
    // 북쪽에서 남쪽으로 내려와야하므로 중심이 (y, x)에 위치할때의 범위와 (y-1, x)에 위치할떄의 범위 모두 확인합니다
    private static boolean canGo(int y, int x) {
        boolean flag = 0 <= x - 1 && x + 1 < C && y + 1 < R + 3;
        flag = flag && (A[y - 1][x - 1] == 0);
        flag = flag && (A[y - 1][x] == 0);
        flag = flag && (A[y - 1][x + 1] == 0);
        flag = flag && (A[y][x - 1] == 0);
        flag = flag && (A[y][x] == 0);
        flag = flag && (A[y][x + 1] == 0);
        flag = flag && (A[y + 1][x] == 0);
        return flag;
    }

    // 정령이 움직일 수 있는 모든 범위를 확인하고 도달할 수 있는 최하단 행을 반환합니다
    private static int bfs(int y, int x) {
        int result = y;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visit = new boolean[MAX_L + 3][MAX_L];
        q.offer(new int[]{y, x});
        visit[y][x] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int k = 0; k < 4; k++) {
                int ny = cur[0] + dy[k], nx = cur[1] + dx[k];
                // 정령의 움직임은 골렘 내부이거나
                // 골렘의 탈출구에 위치하고 있다면 다른 골렘으로 옮겨 갈 수 있습니다
                if (inRange(ny, nx) && !visit[ny][nx] && (A[ny][nx] == A[cur[0]][cur[1]] || (A[ny][nx] != 0 && isExit[cur[0]][cur[1]]))) {
                    q.offer(new int[]{ny, nx});
                    visit[ny][nx] = true;
                    result = Math.max(result, ny);
                }
            }
        }
        return result;
    }

    // 골렘id가 중심 (y, x), 출구의 방향이 d일때 규칙에 따라 움직임을 취하는 함수입니다
    // 1. 남쪽으로 한 칸 내려갑니다.
    // 2. (1)의 방법으로 이동할 수 없으면 서쪽 방향으로 회전하면서 내려갑니다.
    // 3. (1)과 (2)의 방법으로 이동할 수 없으면 동쪽 방향으로 회전하면서 내려갑니다.
    private static void down(int y, int x, int d, int id) {
        if (canGo(y + 1, x)) {
            // 아래로 내려갈 수 있는 경우입니다
            down(y + 1, x, d, id);
        } else if (canGo(y + 1, x - 1)) {
            // 왼쪽 아래로 내려갈 수 있는 경우입니다
            down(y + 1, x - 1, (d + 3) % 4, id);
        } else if (canGo(y + 1, x + 1)) {
            // 오른쪽 아래로 내려갈 수 있는 경우입니다
            down(y + 1, x + 1, (d + 1) % 4, id);
        } else {
            // 1, 2, 3의 움직임을 모두 취할 수 없을떄 입니다.
            if (!inRange(y-1, x-1) || !inRange(y+1, x+1)) {
                // 숲을 벗어나는 경우 모든 골렘이 숲을 빠져나갑니다
                resetMap();
            } else {
                // 골렘이 숲 안에 정착합니다
                A[y][x] = id;
                for (int k = 0; k < 4; k++)
                    A[y + dy[k]][x + dx[k]] = id;
                // 골렘의 출구를 기록하고
                isExit[y + dy[d]][x + dx[d]] = true;
                // bfs를 통해 정령이 최대로 내려갈 수 있는 행를 계산하여 누적합합니다
                answer += bfs(y, x) - 3 + 1;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        R = scanner.nextInt();
        C = scanner.nextInt();
        K = scanner.nextInt();
        for (int id = 1; id <= K; id++) { // 골렘 번호 id
            int x = scanner.nextInt() - 1;
            int d = scanner.nextInt();
            down(0, x, d, id);
        }
        System.out.println(answer);
    }
}