[Codetree] 포탑 부수기

2023 상반기 오전 1번 문제

순수 시간 5시간 정도 갈아 넣은 끝에 구현한 포탑 부수기..

처음에 문제 이해하고 설계를 했으나 객체지향 특징은 잘 못 살리고 절차지향으로 설계해서 디버깅이 오래 걸렸다

 

1차 구현은 2시간 안으로 됐는데, 제공하는 테케 2개를 다 맞히고 나머지 히든을 맞춰보다가 계속 틀렸다.

 

2% 4% 6% 8%에서 계속 끊겼었음..

 

제출 코드

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

public class Main {
    private static Tower[][] board;
    private static int n;
    private static int m;
    private static int k;
    private static boolean[][] previousAttack;
    private static boolean[][] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        board = new Tower[n][m];
        previousAttack = new boolean[n][m];
        visited = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                board[i][j] = new Tower(
                    i, j,
                    Integer.parseInt(st.nextToken())
                );
            }
        }        

        for(int i = 1; i <= k; i++) {
            int[] attacker = selectAttacker();
            if (attacker == null) break;
            // 공격자도 공격 관련에 포함
            previousAttack[attacker[0]][attacker[1]] = true;
            // 최근 공격 저장
            board[attacker[0]][attacker[1]].attackHistory = i;
            // 버프
            board[attacker[0]][attacker[1]].power += (n+m);
            // System.out.println(attacker[0] + ", " + attacker[1]);
            int[] victim = selectVictim(attacker);
            if (victim == null) break;

            // System.out.println(victim[0] + ", " + victim[1]);
            attack(attacker, victim);
            repair();
            if (countAliveTowers() <= 1) break;
        }
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                max = Math.max(max, board[i][j].power);
            }
        }
        System.out.println(max);
    }

    private static int countAliveTowers() {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j].power > 0) cnt++;
            }
        }
        return cnt;
    }


    private static int[] selectAttacker() {
        int minPower = Integer.MAX_VALUE;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j].power != 0) {
                    minPower = Math.min(minPower, board[i][j].power);
                }
            }
        }

        if(minPower == Integer.MAX_VALUE) return null;

        List<Tower> smallerPower = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j].power != 0) {
                    if(board[i][j].power == minPower) {
                        smallerPower.add(board[i][j]);
                    }
                }                                       
            }
        }

        if(smallerPower.size() == 1) {
            // 1. 공격력 가장 낮은 포탑 (1개)
            return new int[]{smallerPower.get(0).x, smallerPower.get(0).y};
        } else {
            // 2. 가장 최근 공격
            Collections.sort(smallerPower, new Comparator<Tower>() {
                @Override
                public int compare(Tower t1, Tower t2) {
                    return Integer.compare(t2.attackHistory, t1.attackHistory);
                }
            });
            int recentMin = smallerPower.get(0).attackHistory;
            List<Tower> recent = new ArrayList<>();
            for(int i = 0; i < smallerPower.size(); i++) {
                if(smallerPower.get(i).attackHistory == recentMin) {
                    recent.add(smallerPower.get(i));
                }
            }

            if(recent.size() == 1) {
                return new int[]{recent.get(0).x, recent.get(0).y};
            } else {
                // 3. 행 열 합 가장 큰
                Collections.sort(recent, new Comparator<Tower>() {
                    @Override
                    public int compare(Tower t1, Tower t2) {
                        return Integer.compare(t2.x + t2.y, t1.x + t1.y);
                    }
                });
                int rowColSumMax = recent.get(0).x + recent.get(0).y;
                List<Tower> rowColSum = new ArrayList<>();
                for(int i = 0; i < recent.size(); i++) {
                    if(recent.get(i).x + recent.get(i).y == rowColSumMax) {
                        rowColSum.add(recent.get(i));
                    }
                }
                                    
                if(rowColSum.size() == 1) {
                    return new int[]{rowColSum.get(0).x, rowColSum.get(0).y};
                } else {
                    // 4. 열 가장 큰
                    Collections.sort(rowColSum, new Comparator<Tower>() {
                        @Override
                        public int compare(Tower t1, Tower t2) {
                            return Integer.compare(t2.y, t1.y);
                        }
                    });
                    return new int[]{rowColSum.get(0).x, rowColSum.get(0).y};
                }
            }
        }
    } // selectAttacker()

    private static int[] selectVictim(int[] attacker) {
        int maxPower = Integer.MIN_VALUE;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j].power != 0 && !(i == attacker[0] && j == attacker[1])) {
                    maxPower = Math.max(maxPower, board[i][j].power);
                }
            }
        }
        
        if(maxPower == Integer.MIN_VALUE) return null;

        List<Tower> biggestPower = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j].power != 0) {
                    if(board[i][j].power == maxPower && !(i == attacker[0] && j == attacker[1])) {
                        biggestPower.add(board[i][j]);
                    }
                }                                       
            }
        }

        if(biggestPower.size() == 1) {
            // 1. 공격력 가장 높은 포탑 (1개)
            return new int[]{biggestPower.get(0).x, biggestPower.get(0).y};
        } else {
            // 2. 가장 오래된 공격
            Collections.sort(biggestPower, new Comparator<Tower>() {
                @Override
                public int compare(Tower t1, Tower t2) {
                    return Integer.compare(t1.attackHistory, t2.attackHistory);
                }
            });
            int recentMin = biggestPower.get(0).attackHistory;
            List<Tower> recent = new ArrayList<>();
            for(int i = 0; i < biggestPower.size(); i++) {
                if(biggestPower.get(i).attackHistory == recentMin) {
                    recent.add(biggestPower.get(i));
                }
            }

            if(recent.size() == 1) {
                return new int[]{recent.get(0).x, recent.get(0).y};
            } else {
                // 3. 행 열 합 가장 작은
                Collections.sort(recent, new Comparator<Tower>() {
                    @Override
                    public int compare(Tower t1, Tower t2) {
                        return Integer.compare(t1.x + t1.y, t2.x + t2.y);
                    }
                });
                int rowColSumMax = recent.get(0).x + recent.get(0).y;
                List<Tower> rowColSum = new ArrayList<>();
                for(int i = 0; i < recent.size(); i++) {
                    if(recent.get(i).x + recent.get(i).y == rowColSumMax) {
                        rowColSum.add(recent.get(i));
                    }
                }
                                    
                if(rowColSum.size() == 1) {
                    return new int[]{rowColSum.get(0).x, rowColSum.get(0).y};
                } else {
                    // 4. 열 가장 작은
                    Collections.sort(rowColSum, new Comparator<Tower>() {
                        @Override
                        public int compare(Tower t1, Tower t2) {
                            return Integer.compare(t1.y, t2.y);
                        }
                    });
                    return new int[]{rowColSum.get(0).x, rowColSum.get(0).y};
                }
            }
        }
    } // selectVictim()

    private static void attack(int[] attacker, int[] target) {
        visited = new boolean[n][m];
        Queue<Point> queue = new LinkedList<>();
        List<int[]> tmp = new ArrayList<>();
        tmp.add(new int[]{attacker[0], attacker[1]});
        Point start = new Point(attacker[0], attacker[1], tmp);
        queue.offer(start);
        visited[attacker[0]][attacker[1]] = true;
        Point shortestPathPoint = null;
        while(!queue.isEmpty()) {
            Point current = queue.poll();
            int cx = current.x;
            int cy = current.y;
            // System.out.println("POLL " + current + ": " + cx + ", " + cy);
            if(cx == target[0] && cy == target[1]) {
                // 최단거리 탐색 완료
                shortestPathPoint = current;
                break;
            }
            int[] dx = {0, 1, 0, -1};
            int[] dy = {1, 0, -1, 0};

            for(int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                // 경계 벗어난다면 반대편으로
                if(nx < 0) nx = n-1;
                if(nx >= n) nx = 0;
                if(ny < 0) ny = m-1;
                if(ny >= m) ny = 0;
                if(board[nx][ny].power != 0 && !visited[nx][ny]) {
                    List<int[]> newPath = new ArrayList<>(current.path);
                    newPath.add(new int[]{nx, ny});
                    queue.offer(new Point(nx, ny, newPath));
                    visited[nx][ny] = true;

                    // System.out.println("OFFER " + input + ": " + nx + ", " + ny);
                    visited[nx][ny] = true;
                }
            }
        } // while
        // System.out.println("SHORTEST PATH");
        // if(shortestPathPoint != null ) {
        //         for(int i = 0 ; i < shortestPathPoint.path.size() ; i++) {
        //         System.out.print(shortestPathPoint.path.get(i)[0] + ", " + shortestPathPoint.path.get(i)[1]);
        //         System.out.println();
        //     }
        // }
        // System.out.println();
        if(shortestPathPoint == null) {
            // 포탄 공격
            // print();
            // System.out.println("POTAN");
            potanAttack(attacker, target);
            // print();
        } else {
            // 레이저 공격 로직
            // print();
            // System.out.println("LAZER");
            lazerAttack(attacker, shortestPathPoint);
            // print();
        }
    } // attack(int[], int[])
    private static void lazerAttack(int[] attacker, Point target) {
        // System.out.println("LAZER ATTACK");
        List<int[]> path = target.path;
        int attackerPower = board[attacker[0]][attacker[1]].power;

        for(int i = 0; i < path.size(); i++) {
            int x = path.get(i)[0];
            int y = path.get(i)[1];
            // System.out.println("LAZER :" + x + ", " + y);
            if(i == path.size() - 1) {
                // 공격지점
                // System.out.println(board[x][y].power + " -= " + attackerPower);
                int result = board[x][y].power - attackerPower;
                board[x][y].power = (result < 0 ? 0 : result);
            } else if(i != 0) {
                // 경로
                // System.out.println(board[x][y].power + " -= " + attackerPower/2);
                int result = board[x][y].power - attackerPower/2;
                board[x][y].power = (result < 0 ? 0 : result);
            }
            previousAttack[x][y] = true;
        }
    }
    private static void potanAttack(int[] attacker, int[] target) {
        // System.out.println("POTAN ATTACK");
        int attackPower = board[attacker[0]][attacker[1]].power;
        int targetX = target[0];
        int targetY = target[1];
        int targetAttackResult = board[targetX][targetY].power - attackPower;
        board[targetX][targetY].power = targetAttackResult < 0 ? 0 : targetAttackResult;
        previousAttack[targetX][targetY] = true;
        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
        for(int i = 0; i < dx.length; i++) {
            int nx = targetX + dx[i];
            int ny = targetY + dy[i];

            // 경계 벗어난다면 반대편으로
            if(nx < 0) nx = n - 1;
            if(nx >= n) nx = 0;
            if(ny < 0) ny = m - 1;
            if(ny >= m) ny = 0;

            // 자신은 제외
            if(nx == attacker[0] && ny == attacker[1]) continue;

            int result = board[nx][ny].power - attackPower/2;
            board[nx][ny].power = result < 0 ? 0 : result;
            previousAttack[nx][ny] = true;
        }
    }
    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].power + " ");
            }
            System.out.println();
        }
    }
    private static void repair() {
        // System.out.println("REPAIR");
        for(int i = 0 ; i < board.length ; i++) {
            for(int j = 0 ; j < board[i].length ; j++) {
                if(!previousAttack[i][j]) {
                    if(board[i][j].power != 0) {
                        board[i][j].power += 1;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            Arrays.fill(previousAttack[i], false);
        }
    }
}

class Tower {
    int x;
    int y;
    int power;
    int attackHistory;
    
    public Tower(int x, int y, int power) {
        this.x = x;
        this.y = y;
        this.power = power;
        this.attackHistory = 0;
    }
}
class Point {
        int x;
        int y;
        List<int[]> path;
        public Point(int x, int y, List<int[]> path) {
            this.x = x;
            this.y = y;
            this.path = path;
        }
    }

 

정답 코드를 보니 내 코드가 얼마나 더러운지 실감이 됐다..

 

Codetree 제공 모범답안 코드

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;

class Pair {
    int x, y;

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

// class turret을 정의해 관리합니다.
class Turret implements Comparable<Turret> {
    int x, y, r, p;

    public Turret(int x, int y, int r, int p) {
        this.x = x;
        this.y = y;
        this.r = r;
        this.p = p;
    }

    // turret의 약함, 강함 우선순위에 맞게 정렬함수를 만들어줍니다.
    public int compareTo(Turret t) {
        if(this.p != t.p) return this.p - t.p;
        if(this.r != t.r) return t.r - this.r;
        if(this.x + this.y != t.x + t.y) return (t.x + t.y) - (this.x + this.y);
        return t.y - this.y;
    }
};

public class Main {
    public static final int MAX_N = 10;
    
    public static int[] dx = new int[]{0, 1, 0, -1};
    public static int[] dy = new int[]{1, 0, -1, 0};
    public static int[] dx2 = new int[]{0, 0, 0, -1, -1, -1, 1, 1, 1};
    public static int[] dy2 = new int[]{0, -1, 1, 0, -1, 1, 0, -1, 1};
    
    public static int n, m, k;
    public static int turn;
    
    // 현재 포탑들이 가진 힘과 언제 각성했는지 기록해줍니다.
    public static int[][] board = new int[MAX_N][MAX_N];
    public static int[][] rec = new int[MAX_N][MAX_N];
    
    // 빛의 공격을 할 때 방문 여부와 경로 방향을 기록해줍니다.
    public static boolean[][] vis = new boolean[MAX_N][MAX_N];
    public static int[][] backX = new int[MAX_N][MAX_N];
    public static int[][] backY = new int[MAX_N][MAX_N];
    
    // 공격과 무관했는지 여부를 저장합니다.
    public static boolean[][] isActive = new boolean[MAX_N][MAX_N];
    
    // 살아있는 포탑들을 관리합니다.
    public static ArrayList<Turret> liveTurret = new ArrayList<>();
    
    // 턴을 진행하기 전 필요한 전처리를 정리해줍니다.
    public static void init() {
        turn++;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                vis[i][j] = false;
                isActive[i][j] = false;
            }
    }
    
    // 각성을 진행합니다.
    // 각성을 하면 가장 약한 포탑이 n + m만큼 강해집니다.
    public static void awake() {
        // 우선순위에 맞게 현재 살아있는 포탑들을 정렬해줍니다.
        Collections.sort(liveTurret);
    
        // 가장 약한 포탑을 찾아 n + m만큼 더해주고,
        // isActive와 liveTurret 배열도 갱신해줍니다.
        Turret weakTurret = liveTurret.get(0);
        int x = weakTurret.x;
        int y = weakTurret.y;
    
        board[x][y] += n + m;
        rec[x][y] = turn;
        weakTurret.p = board[x][y];
        weakTurret.r = rec[x][y];
        isActive[x][y] = true;
    
        liveTurret.set(0, weakTurret);
    }
    
    // 레이저 공격을 진행합니다.
    public static boolean laserAttack() {
        // 기존에 정렬된 가장 앞선 포탑이
        // 각성한 포탑입니다.
        Turret weakTurret = liveTurret.get(0);
        int sx = weakTurret.x;
        int sy = weakTurret.y;
        int pow = weakTurret.p;
    
        // 기존에 정렬된 가장 뒤 포탑이
        // 각성한 포탑을 제외한 포탑 중 가장 강한 포탑입니다.
        Turret strongTurret = liveTurret.get(liveTurret.size() - 1);
        int ex = strongTurret.x;
        int ey = strongTurret.y;
    
        // bfs를 통해 최단경로를 관리해줍니다.
        Queue<Pair> q = new LinkedList<>();
        vis[sx][sy] = true;
        q.add(new Pair(sx, sy));
    
        // 가장 강한 포탑에게 도달 가능한지 여부를 canAttack에 관리해줍니다.
        boolean canAttack = false;
    
        while(!q.isEmpty()) {
            int x = q.peek().x;
            int y = q.peek().y;
            q.poll();
    
            // 가장 강한 포탑에게 도달할 수 있다면
            // 바로 멈춥니다.
            if(x == ex && y == ey) {
                canAttack = true;
                break;
            }
    
            // 각각 우, 하, 좌, 상 순서대로 방문하며 방문 가능한 포탑들을 찾고
            // queue에 저장해줍니다.
            for(int dir = 0; dir < 4; dir++) {
                int nx = (x + dx[dir] + n) % n;
                int ny = (y + dy[dir] + m) % m;
    
                // 이미 방문한 포탑이라면 넘어갑니다.
                if(vis[nx][ny]) 
                    continue;
    
                // 벽이라면 넘어갑니다.
                if(board[nx][ny] == 0) 
                    continue;
    
                vis[nx][ny] = true;
                backX[nx][ny] = x;
                backY[nx][ny] = y;
                q.add(new Pair(nx, ny));
            }
        }
    
        // 만약 도달 가능하다면 공격을 진행합니다.
        if(canAttack) {
            // 우선 가장 강한 포탑에게는 pow만큼의 공격을 진행합니다.
            board[ex][ey] -= pow;
            if(board[ex][ey] < 0) 
                board[ex][ey] = 0;
            isActive[ex][ey] = true;
    
            // 기존의 경로를 역추적하며
            // 경로 상에 있는 모든 포탑에게 pow / 2만큼의 공격을 진행합니다.
            int cx = backX[ex][ey];
            int cy = backY[ex][ey];
    
            while(!(cx == sx && cy == sy)) {
                board[cx][cy] -= pow / 2;
                if(board[cx][cy] < 0) 
                    board[cx][cy] = 0;
                isActive[cx][cy] = true;
    
                int nextCx = backX[cx][cy];
                int nextCy = backY[cx][cy];
    
                cx = nextCx;
                cy = nextCy;
            }
        }
    
        // 공격을 성공했는지 여부를 반환합니다.
        return canAttack;
    }
    
    // 레이저 공격을 하지 못했다면 폭탄 공격을 진행합니다.
    public static void bombAttack() {
        // 기존에 정렬된 가장 앞선 포탑이
        // 각성한 포탑입니다.
        Turret weakTurret = liveTurret.get(0);
        int sx = weakTurret.x;
        int sy = weakTurret.y;
        int pow = weakTurret.p;
    
        // 기존에 정렬된 가장 뒤 포탑이
        // 각성한 포탑을 제외한 포탑 중 가장 강한 포탑입니다.
        Turret strongTurret = liveTurret.get(liveTurret.size() - 1);
        int ex = strongTurret.x;
        int ey = strongTurret.y;
    
        // 가장 강한 포탑의 3 * 3 범위를 모두 탐색하며
        // 각각에 맞는 공격을 진행합니다.
        for(int dir = 0; dir < 9; dir++) {
            int nx = (ex + dx2[dir] + n) % n;
            int ny = (ey + dy2[dir] + m) % m;
    
            // 각성한 포탑 자기 자신일 경우 넘어갑니다.
            if(nx == sx && ny == sy) 
                continue;
    
            // 가장 강한 포탑일 경우 pow만큼의 공격을 진행합니다.
            if(nx == ex && ny == ey) {
                board[nx][ny] -= pow;
                if(board[nx][ny] < 0) 
                    board[nx][ny] = 0;
                isActive[nx][ny] = true;
            }
            // 그 외의 경우 pow / 2만큼의 공격을 진행합니다.
            else {
                board[nx][ny] -= pow / 2;
                if(board[nx][ny] < 0) 
                    board[nx][ny] = 0;
                isActive[nx][ny] = true;
            }
        }
    }
    
    // 공격에 관여하지 않은 모든 살아있는 포탑의 힘을 1 증가시킵니다.
    public static void reserve() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(isActive[i][j]) 
                    continue;
                if(board[i][j] == 0) 
                    continue;
                board[i][j]++;
            }
        }
    }

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

        // 입력:
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                board[i][j] = sc.nextInt();

        // k턴 동안 진행됩니다.
        while(k-- > 0) {
            // 턴을 진행하기 전 살아있는 포탑을 정리합니다.
            liveTurret = new ArrayList<>();
            for(int i = 0; i < n; i++)
                for(int j = 0; j < m; j++)
                    if(board[i][j] > 0) {
                        Turret newTurret = new Turret(i, j, rec[i][j], board[i][j]);
                        liveTurret.add(newTurret);
                    }

            // 살아있는 포탑이 1개 이하라면 바로 종료합니다.
            if(liveTurret.size() <= 1) 
                break;

            // 턴을 진행하기 전 필요한 전처리를 정리해줍니다.
            init();

            // 각성을 진행합니다.
            awake();

            // 레이저 공격을 진행합니다.
            boolean isSuc = laserAttack();
            // 레이저 공격을 하지 못했다면 포탄 공격을 진행합니다.
            if(!isSuc) 
                bombAttack();

            // 공격에 관여하지 않은 모든 살아있는 포탑의 힘을 1 증가시킵니다.
            reserve();
        }

        // 살아있는 포탑의 힘 중 가장 큰 값을 출력합니다.
        int ans = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                ans = Math.max(ans, board[i][j]);

        Systehttp://m.out.print(ans);
    }
}

디버깅 포인트

1. int dx int dy 경계 처리 잘 하기 (모서리 넘어갈 때)
2. 모든 포탑 공격력 0 시에 턴 더 진행하지 않고 턴 종료
3. 레이저 공격 루트에서 공격자 제외
4. 공격 루트 넣어줄 때 그냥 새로운 리스트 객체 만들기 (재사용하면 참조 어긋날 수 있음)

6. 객체 비교할 일이 있을 때는 Comparable 정의하기.. (인생이 편해질듯)

// class turret을 정의해 관리합니다.
class Turret implements Comparable<Turret> {
    int x, y, r, p;

    public Turret(int x, int y, int r, int p) {
        this.x = x;
        this.y = y;
        this.r = r;
        this.p = p;
    }

    // turret의 약함, 강함 우선순위에 맞게 정렬함수를 만들어줍니다.
    public int compareTo(Turret t) {
        if(this.p != t.p) return this.p - t.p;
        if(this.r != t.r) return t.r - this.r;
        if(this.x + this.y != t.x + t.y) return (t.x + t.y) - (this.x + this.y);
        return t.y - this.y;
    }
};