[Codetree] 왕실의 기사 대결

2023 하반기 오전 1번 문제

첫 설계 1시간 걸리고,

구현 2시간 하고, 디버깅 1시간 하다가 로직이 답이 없음을 깨닫고

정답 코드를 이해하고 구현했다.

 

단순 시뮬레이션으로 구현하려다가, 풀이는 bfs던데 하나의 조각 단위로 밀면서 계산하는 방식이 너무 어려워서..

 

기사 다음 칸 이동 가능한지 검사(DFS)

기사 다음칸 이동(DFS)

 

2중 DFS로 구현했다.

 

답을 알고 구현하는 데에는 1시간, 예외처리 + 테케 맞추는 데에 15분? 정도 걸렸다.

 

체스판(board)에는 빈칸/함정/벽 기록하고

기사판(knightBoard)에는 기사들의 위치를 기록했다

 

그리고 Map<int[]>로 각 기사들의 분포 위치를 (r,c)와 (h,w)에 맞게 넣어주고 contains로 비교하려 했으나..

 

그냥 Knight[] 배열에 참조 테이블을 두어서 그때그때 기록하고, 변경점이 있으면 매번 순회하는 게 디버깅하기 쉬울 것 같아서 그렇게 했다

시간 복잡도가 높아도 삼성 문제는 구현력을 더 중시하는 경향인 것 같아서.. 사실 시간 초과 걱정을 안 해도 돼서 되게 좋았다.

 

그렇게 구현하고, DFS 무한 재귀 stack overflow가 두어번 발생했지만 오타나 i,j를 잘못 본 것이라 생각외로 구현이 빠르게 되었다.

 

정답을 보고 힌트를 얻어 구현한 거라,, 깨달은 점이 많진 않지만

 

1. 사망한 기사에 대한 명령 시 스킵하기(("포탑 부수기") 에서도 전체 테케에 대한 예외처리가 필수였다)

2. DFS 조건 잘 짜기

3. 수도 코드 무조건 짜고 들어가기 (전체 로직에서 절차적 프로그래밍 하듯이)

4. 자료구조 선택 (Knight[], board를 두개 둔 것 등)

 

번외로, 여태 PS 풀면서 재밌다 느낀 적 별로 없었는데,, 삼성 코테는 스트레스도 받지만 생각보다 재밌네요!

 

 

제출 코드

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

public class Main {
    private static int L;
    private static int N;
    private static int Q;
    private static int[][] board, knightBoard;
    private static Knight[] knightStatus;
    private static int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static boolean[] moved;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        board = new int[L][L];
        knightBoard = new int[L][L];
        knightStatus = new Knight[N+1];
        moved = new boolean[N+1];
        // 체스판 초기화
        for(int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < L; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 초기 기사 정보
        for(int knightNumber = 1; knightNumber <= N; knightNumber++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            putKnightsOnTheBoard(knightNumber, r - 1, c - 1, h, w, k);
        }
        // print(board);
        // print(knightBoard);
        // printKnightStatus();

        for(int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int commandKnight = Integer.parseInt(st.nextToken());
            int direction = Integer.parseInt(st.nextToken());

            if(knightStatus[commandKnight].alive){
                execute(commandKnight, direction);
            }
        }

        int answer = 0;
        for(int i = 1; i < knightStatus.length; i++) {
            Knight node = knightStatus[i];
            // System.out.println(i + "번 기사(" + node.alive + ") 누적 데미지: " + node.damage);
            if(node.alive) {
                answer += node.damage;
            }
        }
        System.out.println(answer);
    }

    private static void printKnightStatus() {
        for(int i = 1 ; i < knightStatus.length ; i++) {
            System.out.println(knightStatus[i].row);
            System.out.println(knightStatus[i].column);
            System.out.println(knightStatus[i].height);
            System.out.println(knightStatus[i].width);
            System.out.println(knightStatus[i].power);
        }
    }

    private static void putKnightsOnTheBoard(int knightNumber, int r, int c, int h, int w, int k) {
        for(int i = r; i < r + h; i++) {
            for(int j = c; j < c + w; j++) {
                knightBoard[i][j] = knightNumber;
            }
        }
        knightStatus[knightNumber] = new Knight(r, c, h, w, k);
    }

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

    private static void execute(int commandKnight, int direction) {
        // System.out.println(commandKnight + " MOVE TO " + direction);
        // 움직일 수 없으면 continue;
        if(!canMove(commandKnight, direction)) {
            // System.out.println(commandKnight + "CAN'T MOVE");
            return;
        }
        // System.out.println("CAN MOVE!!");
        // 이동
        moveKnight(commandKnight, direction);
        // print(knightBoard);
        // 데미지 계산(commandKnight 제외)
        calculateDamage(commandKnight);
        // print(knightBoard);
        Arrays.fill(moved, false);
    }

    private static void calculateDamage(int excludeKnight) {
        for (int i = 1; i <= N; i++) {
            if (!moved[i] || i == excludeKnight || !knightStatus[i].alive) continue;

            int damage = 0;
            Knight knight = knightStatus[i];

            for (int r = knight.row; r < knight.row + knight.height; r++) {
                for (int c = knight.column; c < knight.column + knight.width; c++) {
                    if (board[r][c] == 1) {
                        damage++;
                    }
                }
            }

            knight.power -= damage;
            knight.damage += damage;

            if (knight.power <= 0) {
                killKnight(i);
            }
        }
    }


    private static void killKnight(int knightNumber) {
        knightStatus[knightNumber].alive = false;
        for(int i = 0; i < L; i++) {
            for(int j = 0; j < L; j++) {
                if(knightBoard[i][j] == knightNumber) {
                    knightBoard[i][j] = 0;
                }
            }
        }
    }

    private static boolean canMove(int knightNumber, int direction) {
        int row = knightStatus[knightNumber].row;
        int column = knightStatus[knightNumber].column;
        int height = knightStatus[knightNumber].height;
        int width = knightStatus[knightNumber].width;
        // System.out.println("TRY " + knightNumber + "(" + row + ", " + column + ") MOVE TO " + direction);
        
        for(int i = row; i < row + height; i++) {
            for(int j = column; j < column + width; j++) {
                int nr = i + directions[direction][0];
                int nc = j + directions[direction][1];

                // 벽 체크
                if(isWall(nr,nc)) {
                    return false;
                }

                int next = knightBoard[nr][nc];

                if(next == 0 || next == (knightNumber)) {
                    continue;
                }

                if(!canMove(next, direction)) {
                    return false;
                }
            }
        }
        return true;
    }

    static boolean isWall(int r, int c) {
        return r < 0 || c < 0 || r >= L || c >= L || board[r][c] == 2;
    }
    
    private static void moveKnight(int knightNumber, int direction) {
        int row = knightStatus[knightNumber].row;
        int column = knightStatus[knightNumber].column;
        int height = knightStatus[knightNumber].height;
        int width = knightStatus[knightNumber].width;
        // System.out.println("MOVE " + knightNumber + "(" + row + ", " + column + ") MOVE TO " + direction);

        for(int i = row; i < row + height; i++) {
            for(int j = column; j < column + width; j++) {
                int nr = i + directions[direction][0];
                int nc = j + directions[direction][1];

                int next = knightBoard[nr][nc];

                if(next == 0 || next == knightNumber) {
                    continue;
                }
                
                moveKnight(next, direction);
            }
        }

        moved[knightNumber] = true;

        switch(direction) {
            case 0:
                moveUp(knightNumber, direction);
                break;
            case 1:
                moveRight(knightNumber, direction);
                break;
            case 2:
                moveDown(knightNumber, direction);
                break;
            case 3:
                moveLeft(knightNumber, direction);
                break;
        }

        knightStatus[knightNumber].row += directions[direction][0];
        knightStatus[knightNumber].column += directions[direction][1];
    }

    private static void moveUp(int knightNumber, int direction) {
        int row = knightStatus[knightNumber].row;
        int column = knightStatus[knightNumber].column;
        int height = knightStatus[knightNumber].height;
        int width = knightStatus[knightNumber].width;

        for (int r = row; r < row + height; r++) {
            for (int c = column; c < column + width; c++) {
                int nr =  r + directions[direction][0];
                int nc =  c + directions[direction][1];

                knightBoard[r][c] = 0;
                knightBoard[nr][nc] = (knightNumber);
            }
        }
    }

    private static void moveRight(int knightNumber, int direction) {
        int row = knightStatus[knightNumber].row;
        int column = knightStatus[knightNumber].column;
        int height = knightStatus[knightNumber].height;
        int width = knightStatus[knightNumber].width;

        for (int c = column + width - 1; c >= column; c--) {
            for (int r = row; r < row + height; r++) {
                int nr =  r + directions[direction][0];
                int nc =  c + directions[direction][1];

                knightBoard[r][c] = 0;
                knightBoard[nr][nc] = (knightNumber);
            }
        }
    }

    private static void moveDown(int knightNumber, int direction) {
        int row = knightStatus[knightNumber].row;
        int column = knightStatus[knightNumber].column;
        int height = knightStatus[knightNumber].height;
        int width = knightStatus[knightNumber].width;

        for (int r = row + height - 1; r >= row; r--) {
            for (int c = column; c < column + width; c++) {
                int nr =  r + directions[direction][0];
                int nc =  c + directions[direction][1];

                knightBoard[r][c] = 0;
                knightBoard[nr][nc] = (knightNumber);
            }
        }
    }

    private static void moveLeft(int knightNumber, int direction) {
        int row = knightStatus[knightNumber].row;
        int column = knightStatus[knightNumber].column;
        int height = knightStatus[knightNumber].height;
        int width = knightStatus[knightNumber].width;

        for (int c = column; c < column + width; c++) {
            for (int r = row; r < row + height; r++) {
                int nr =  r + directions[direction][0];
                int nc =  c + directions[direction][1];

                knightBoard[r][c] = 0;
                knightBoard[nr][nc] = (knightNumber);
            }
        }
    }
}

class Knight {
    int row;
    int column;
    int height;
    int width;
    int power;
    int damage = 0;
    boolean alive = true;

    public Knight(int row, int column, int height, int width, int power) {
        this.row = row;
        this.column = column;
        this.height = height;
        this.width = width;
        this.power = power;
        this.alive = true;
    }
}

 

정답 코드

import java.util.*;

public class Main {
    public static final int MAX_N = 31;
    public static final int MAX_L = 41;

    public static int l, n, q;
    public static int[][] info = new int[MAX_L][MAX_L];
    public static int[] bef_k = new int[MAX_N];
    public static int[] r = new int[MAX_N], c = new int[MAX_N], h = new int[MAX_N], w = new int[MAX_N], k = new int[MAX_N];
    public static int[] nr = new int[MAX_N], nc = new int[MAX_N];
    public static int[] dmg = new int[MAX_N];
    public static boolean[] is_moved = new boolean[MAX_N];

    public static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};

    // 움직임을 시도해봅니다.
    public static boolean tryMovement(int idx, int dir) {
        Queue<Integer> q = new LinkedList<>();
        boolean is_pos = true;

        // 초기화 작업입니다.
        for(int i = 1; i <= n; i++) {
            dmg[i] = 0;
            is_moved[i] = false;
            nr[i] = r[i];
            nc[i] = c[i];
        }

        q.add(idx);
        is_moved[idx] = true;

        while(!q.isEmpty()) {
            int x = q.poll();

            nr[x] += dx[dir];
            nc[x] += dy[dir];

            // 경계를 벗어나는지 체크합니다.
            if(nr[x] < 1 || nc[x] < 1 || nr[x] + h[x] - 1 > l || nc[x] + w[x] - 1 > l)
                return false;

            // 대상 조각이 다른 조각이나 장애물과 충돌하는지 검사합니다.
            for(int i = nr[x]; i <= nr[x] + h[x] - 1; i++) {
                for(int j = nc[x]; j <= nc[x] + w[x] - 1; j++) {
                    if(info[i][j] == 1) 
                        dmg[x]++;
                    if(info[i][j] == 2)
                        return false;
                }
            }

            // 다른 조각과 충돌하는 경우, 해당 조각도 같이 이동합니다.
            for(int i = 1; i <= n; i++) {
                if(is_moved[i] || k[i] <= 0) 
                    continue;
                if(r[i] > nr[x] + h[x] - 1 || nr[x] > r[i] + h[i] - 1) 
                    continue;
                if(c[i] > nc[x] + w[x] - 1 || nc[x] > c[i] + w[i] - 1) 
                    continue;

                is_moved[i] = true;
                q.add(i);
            }
        }

        dmg[idx] = 0;
        return true;
    }

    // 특정 조각을 지정된 방향으로 이동시키는 함수입니다.
    public static void movePiece(int idx, int dir) {
        if(k[idx] <= 0) return;

        // 이동이 가능한 경우, 실제 위치와 체력을 업데이트합니다.
        if(tryMovement(idx, dir)) {
            for(int i = 1; i <= n; i++) {
                r[i] = nr[i];
                c[i] = nc[i];
                k[i] -= dmg[i];
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력값을 받습니다.
        l = sc.nextInt();
        n = sc.nextInt();
        q = sc.nextInt();

        for(int i = 1; i <= l; i++)
            for(int j = 1; j <= l; j++)
                info[i][j] = sc.nextInt();

        for(int i = 1; i <= n; i++) {
            r[i] = sc.nextInt();
            c[i] = sc.nextInt();
            h[i] = sc.nextInt();
            w[i] = sc.nextInt();
            k[i] = sc.nextInt();
            bef_k[i] = k[i];
        }

        for(int i = 1; i <= q; i++) {
            int idx = sc.nextInt();
            int dir = sc.nextInt();
            movePiece(idx, dir);
        }

        // 결과를 계산하고 출력합니다.
        long ans = 0;
        for(int i = 1; i <= n; i++) {
            if(k[i] > 0) {
                ans += bef_k[i] - k[i];
            }
        }

        System.out.println(ans);
    }
}