[알고리즘] 루돌프의 반란

https://www.codetree.ai/training-field/frequent-problems/problems/rudolph-rebellion/description?page=1&pageSize=20

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

    static class Santa {
        int id;
        int score;
        Point point;
        boolean isStunned;
        int whenNotStunned;
        boolean isDied;

        public Santa(int id, int score, Point point, int power, boolean isStunned,
                int whenNotStunned) {
            this.id = id;
            this.score = score;
            this.point = point;
            this.isStunned = isStunned;
            this.whenNotStunned = whenNotStunned;
            this.isDied = false;
        }

        @Override
        public String toString() {
            return "Santa{" +
                    "id=" + id +
                    ", score=" + score +
                    ", point=" + point +
                    ", isStunned=" + isStunned +
                    ", whenNotStunned=" + whenNotStunned +
                    '}';
        }
    }

    static class Dog {
        Point point;

        public Dog(Point point) {
            this.point = point;
        }

        @Override
        public String toString() {
            return "Dog{" +
                    "point=" + point +
                    '}';
        }
    }


    static int N;
    static int M;
    static int P;
    static int C;
    static int D;
    static TreeSet<Santa> santas;
    static Dog dog;
    static int[] finalScore;
    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());
        P = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        finalScore = new int[P + 1];

        st = new StringTokenizer(br.readLine());
        dog = new Dog(
                new Point(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1));
        santas = new TreeSet<>(new Comparator<Santa>() {
            @Override
            public int compare(Santa o1, Santa o2) {
                return o1.id - o2.id;
            }
        });
        for (int i = 1; i <= P; i++) {
            st = new StringTokenizer(br.readLine());
            Santa santa = new Santa(Integer.parseInt(st.nextToken()), 0,
                    new Point(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1),
                    D,
                    false, 0);
            santas.add(santa);
        }

        for (int i = 1; i <= M; i++) {
            playRound();
//            System.out.println("round = " + i);;
//            System.out.println(dog);
//            for (Santa santa : santas) {
//                System.out.println(santa);
//            }
//            for (int j = 1; j < finalScore.length; j++) {
//                if (finalScore[j] != 0) {
//                    System.out.println("score " + j + " " + finalScore[j]);
//                }
//            }
//            System.out.println();
        }
        StringBuilder sb = new StringBuilder();
        for (Santa santa : santas) {
            finalScore[santa.id] = santa.score;
        }
        for (int i = 1; i < finalScore.length; i++) {
            sb.append(finalScore[i]).append(" ");
        }
        System.out.println(sb);
    }

    private static void playRound() {
        // 산타가 모두 탈락이라면 게임 종료
        if (santas.isEmpty()) {
            return;
        }
        dogMove();
        santasMove();
        // 기절 산타 갱신
        for (Santa santa : santas) {
            if (santa.isStunned) {
                if (santa.whenNotStunned == 0) {
                    santa.isStunned = false;
                } else {
                    santa.whenNotStunned--;
                }
            }
        }
        // 점수 + 1
        for (Santa santa : santas) {
            santa.score++;
        }
    }

    private static void santasMove() {
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        List<Santa> removeSanta = new ArrayList<>();
        for (Santa santa : santas) {
            if (santa.isStunned || santa.isDied) {
                continue;
            }
            Integer dir = moveS(santa, dx, dy);
            if (dir == null) {
                continue;
            }
            Point point;

            // 루돌프와의 충돌 확인

            if (!dog.point.equals(santa.point)) {
                continue;
            }
            // santa 점수 증가
            santa.score += D;
            // santa 기절
            santa.isStunned = true;
            santa.whenNotStunned = 1;
            // santa 이동
            point = santa.point;
//            System.out.println("before " + santa);
            int nr = point.x - dx[dir] * D;
            int nc = point.y - dy[dir] * D;
//            System.out.println(nr + " " + nc);
            if (validateRange(new Point(nr, nc))) {
                // santa 이동
                santa.point.setLocation(nr, nc);
            } else {
                // 최종 점수 등록
                finalScore[santa.id] = santa.score;
                // 삭제
                removeSanta.add(santa);
                santa.isDied = true;
                continue;
            }
            while (isBakSal(santa)) {
                santa = afterCollide(santa, (dir + 2) % 4, new int[] {-1, 0, 1, 0}, new int[] {0, 1, 0, -1}, removeSanta);
                if (santa == null) {
                    break;
                }
            }
        }
        for (Santa santa : removeSanta) {
            santas.remove(santa);
        }
    }

    private static Integer moveS(Santa santa, int[] dx, int[] dy) {
        Point point = null;
        int minDis = (int)(Math.pow(santa.point.x - dog.point.x, 2) + Math.pow(santa.point.y - dog.point.y, 2));
        int dir = -1;
        for (int i = 0; i < 4; i++) {
            int nr = santa.point.x + dx[i];
            int nc = santa.point.y + dy[i];

            if (!validateRange(new Point(nr, nc))) {
                continue;
            }

            if (!validateCollide(new Point(nr, nc))) {
                continue;
            }
            int dr = dog.point.x - nr;
            int dc = dog.point.y - nc;
            int dis = (int)(Math.pow(dr, 2) + Math.pow(dc, 2));
            if (dis < minDis) {
                minDis = dis;
                dir = i;
            }
        }
        if (dir != -1) {
            int nr = santa.point.x + dx[dir];
            int nc = santa.point.y + dy[dir];
            santa.point.setLocation(nr, nc);
        } else {
            return null;
        }
        return dir;
    }

    private static boolean validateCollide(Point point) {
        for (Santa santa1 : santas) {
            if (santa1.isDied) {
                continue;
            }
            if (point.equals(santa1.point)) {
                return false;
            }
        }
        return true;
    }

    private static void dogMove() {
        Santa santa = findSanta();
        int dir = move(santa);
        if (isCollied()) {
            collide(dir);
        }
        while (isBakSal(santa)) {
            santa = afterCollide2(santa, dir, new int[] {-1, -1, -1, 0, 0, 1, 1, 1}, new int[] {-1, 0, 1, -1, 1, -1, 0, 1});
            if (santa == null) {
                break;
            }
        }
    }

    private static Santa afterCollide(Santa santa, int dir, int[] dr, int[] dc, List<Santa> removeSanta) {
        for (Santa santa1 : santas) {
            if (santa1.isDied) {
                continue;
            }
            if (!santa.equals(santa1) && santa.point.equals(santa1.point)) {
                // santa 이동
                Point point = santa1.point;
                int nr = point.x + dr[dir];
                int nc = point.y + dc[dir];
                if (validateRange(new Point(nr, nc))) {
                    // santa 이동
                    santa1.point.setLocation(nr, nc);
                    return santa1;
                } else {
                    // 최종 점수 등록
                    finalScore[santa1.id] = santa1.score;
                    // 삭제
                    removeSanta.add(santa1);
//                    santas.remove(santa1);
                    return null;
                }
            }
        }
        return null;
    }
    private static Santa afterCollide2(Santa santa, int dir, int[] dr, int[] dc) {
        for (Santa santa1 : santas) {
            if (santa1.isDied) {
                continue;
            }
            if (!santa.equals(santa1) && santa.point.equals(santa1.point)) {
                // santa 이동
                Point point = santa1.point;
                int nr = point.x + dr[dir];
                int nc = point.y + dc[dir];
                if (validateRange(new Point(nr, nc))) {
                    // santa 이동
                    santa1.point.setLocation(nr, nc);
                    return santa1;
                } else {
                    // 최종 점수 등록
                    finalScore[santa1.id] = santa1.score;
                    // 삭제
//                    removeSanta.add(santa1);
                    santas.remove(santa1);
                    return null;
                }
            }
        }
        return null;
    }
    private static boolean isBakSal(Santa santa) {
        if (!santas.contains(santa)) {
            return false;
        }
        for (Santa santa1 : santas) {
            if (santa1.isDied) {
                continue;
            }
            if (!santa.equals(santa1) && santa.point.equals(santa1.point)) {
                return true;
            }
        }
        return false;
    }

    private static void collide(int dir) {
        int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
        for (Santa santa : santas) {
//            System.out.println(dog.point + " " + santa.point);
            if (dog.point.equals(santa.point)) {

                // santa 점수 증가
                santa.score += C;
                // santa 기절
                santa.isStunned = true;
                santa.whenNotStunned = 1;
                // santa 이동
                Point point = santa.point;
                int nr = point.x + dr[dir] * C;
                int nc = point.y + dc[dir] * C;
                if (validateRange(new Point(nr, nc))) {
                    // santa 이동
                    santa.point.setLocation(nr, nc);
                } else {
                    // 최종 점수 등록
                    finalScore[santa.id] = santa.score;
                    // 삭제
                    santa.isDied = true;
                    santas.remove(santa);
                }
                return;
            }

        }
    }

    private static boolean isCollied() {
        for (Santa santa : santas) {
            if (dog.point.equals(santa.point)) {
                return true;
            }
        }
        return false;
    }

    private static int move(Santa santa) {
        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
        int minDis = Integer.MAX_VALUE;
        int dir = -1;
        for (int i = 0; i < 8; i++) {
            int nr = dog.point.x + dx[i];
            int nc = dog.point.y + dy[i];

            if (!(validateRange(new Point(nr, nc)))) {
                continue;
            }

            int dr = santa.point.x - nr;
            int dc = santa.point.y - nc;
            int dis = (int)(Math.pow(dr, 2) + Math.pow(dc, 2));
            if (dis < minDis) {
                minDis = dis;
                dir = i;
            }
        }

        int nr = dog.point.x + dx[dir];
        int nc = dog.point.y + dy[dir];

        dog.point.x = nr;
        dog.point.y = nc;
//        System.out.println("dir = " + dir);
//        System.out.println(dog.point);
        return dir;
    }

    private static Santa findSanta() {
        int minDis = Integer.MAX_VALUE;
        Santa temp = null;
        for (Santa santa : santas) {
            int dr = dog.point.x - santa.point.x;
            int dc = dog.point.y - santa.point.y;
            int dis = (int)(Math.pow(dr, 2) + Math.pow(dc, 2));
            if (minDis > dis) {
                minDis = dis;
                temp = santa;
            } else if (minDis == dis) {
                if (temp.point.x == santa.point.x) {
                    temp = temp.point.y > santa.point.y ? temp : santa;
                } else {
                    temp = temp.point.x > santa.point.x ? temp : santa;
                }
            }
        }
//        System.out.println("temp = " + temp);
        return temp;
    }

    private static boolean validateRange(Point point) {
        int r = point.x;
        int c = point.y;
        if (0 <= r && r < N && 0 <= c && c < N) {
            return true;
        }
        return false;
    }

}

나의 풀이

- 빡구현 문제

- 어렵긴 한데 함수를 많이 나누니까 디버깅이 편리한 건 맞는 듯하다.

- 산타가 움직일 때 죽은 산타도 충돌에 고려해주어서 틀렸었다.

- 더 쉽게 짤 수 있는 방법을 고민해보고 설계하자.