[알고리즘] 미로 타워 디펜스

https://www.codetree.ai/training-field/frequent-problems/problems/maze-tower-defense/description?page=2&pageSize=20

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

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

import com.sun.org.apache.xalan.internal.xsltc.dom.CurrentNodeListFilter;

public class Main {

    static class Monster {
        int id;
        Point point;
        public Monster(int id, Point point) {
            super();
            this.id = id;
            this.point = point;
        }


        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((point == null) ? 0 : point.hashCode());
            return result;
        }


        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Monster other = (Monster) obj;
            if (point == null) {
                if (other.point != null)
                    return false;
            } else if (!point.equals(other.point))
                return false;
            return true;
        }


        @Override
        public String toString() {
            return "Monster [id=" + id + ", point=" + point + "]";
        }

    }
    static Point[] pre;
    static int preCount = 0;
    static int n;
    static int m;
    static List<Monster> list;
    static int result = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        pre = new Point[n * n - 1];
        findSpiral();

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

        list = new ArrayList<>();
        for(Point point : pre) {
            int x = point.x;
            int y = point.y;
            if (map[x][y] == 0) {
                break;
            }
            list.add(new Monster(map[x][y], new Point(x, y)));
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            playOneRound(d, p);

        }
        System.out.println(result);
    }
    private static void playOneRound(int d, int p) {
        // 지워지는 좌표 구하기
        List<Point> deletePoints = findDelete(d, p);
        // 좌표 지우기
        for (Point point : deletePoints) {
            for (Monster monster : list) {
                if (monster.point.equals(point)) {
                    result += monster.id;
                    list.remove(monster);
                    break;
                }
            }
        }
        // 연속되는 좌표 없애기
        while(deleteCont2());
        // 짝 지어주기
        makePair();
        // 새로운 좌표로 리스트 만들기
        for (int i = 0; i < list.size(); i++) {
            list.get(i).point = new Point(pre[i].x, pre[i].y);
//			System.out.println(list.get(i));
        }
    }
    private static void makePair() {
        if (list.isEmpty()) {
            return;
        }
        List<Monster> temp = new ArrayList<>();
        int cur = list.get(0).id;
        int count = 1;
        for (int i = 1; i < list.size(); i++) {
            if (cur == list.get(i).id) {
                count++;
            } else {
                temp.add(new Monster(count, null));
                temp.add(new Monster(cur, null));
                count = 1;
                cur = list.get(i).id;
            }
        }
        temp.add(new Monster(count, null));
        temp.add(new Monster(cur, null));
        if (temp.size() > n * n - 1) {
            list = new ArrayList<>();
            for (int i = 0; i < n * n - 1; i++) {
                list.add(temp.get(i));
            }
        } else {
            list = temp;
        }
    }
    private static boolean deleteCont() {
        for (int i = 0; i < list.size(); i++) {
            int cur = list.get(i).id;
            int count = 1;
            for (int j = i+1; j < list.size(); j++) {
                if (cur == list.get(j).id) {
                    count++;
                } else {
                    break;
                }
            }
            if (count >= 4) {
                List<Monster> temp = new ArrayList<>();
                for (int j = i; j < i + count; j++) {
                    temp.add(list.get(j));
                }
                for (Monster monster : temp) {
                    result += monster.id;
                    list.remove(monster);
//					System.out.println("monster " + monster.id);
                }
                return true;
            }
        }
        return false;
    }

    private static boolean deleteCont2() {
        if (list.isEmpty()) {
            return false;
        }
        List<Monster> temp = new ArrayList<>();
        Monster cur = list.get(0);
        int count = 1;
        for (int i = 1; i < list.size(); i++) {
            if (cur.id == list.get(i).id) {
                count++;
            } else {
                if (count >= 4) {
                    for (int j = i - count; j < i; j++) {
                        temp.add(list.get(j));
                    }
                }
                count = 1;
                cur = list.get(i);
            }
        }
        if (count >= 4) {
            for (int j = list.size() - count; j < list.size(); j++) {
                temp.add(list.get(j));
            }
        }
        if (temp.isEmpty()) {
            return false;
        } else {
            for (Monster monster : temp) {
                result += monster.id;
                list.remove(monster);
            }
            return true;
        }

    }
    private static List<Point> findDelete(int d, int p) {
        Point mid = new Point(n/2, n/2);
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        List<Point> results = new ArrayList<>();
        for (int i = 0; i < p; i++) {
            mid.x = mid.x + dx[d];
            mid.y = mid.y + dy[d];
            results.add(new Point(mid.x, mid.y));
        }
        return results;
    }
    private static void findSpiral() {
        Point curPoint = new Point(n/2, n/2);
        int[] dx = {0, 1, 0, -1};
        int[] dy = {-1, 0, 1, 0};
        int dir = 0;
        int step = 1;
        out: while (true) {
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < step; j++) {
                    curPoint.x = curPoint.x + dx[dir];
                    curPoint.y = curPoint.y + dy[dir];
                    if (!(0 <= curPoint.x && curPoint.x < n && 0 <= curPoint.y && curPoint.y < n)) {
                        break out;
                    }
                    pre[preCount++] = new Point(curPoint.x, curPoint.y);
                }
                dir = (dir+1) % 4;
            }
            step++;
        }
    }


}

나의 풀이

- 이 문제도 역시나 문제를 잘못 이해해서 틀렸었다. 연속된 4개 이상의 같은 종류의 몬스터를 동시에 없애는데 그걸 고려하지 않았다. 주의하자!!! 하라는 대로 하자!!!

- 연속된 숫자를 제거해줄 때 이미 지나온 숫자들을 없애주어야 하는데 그 방향을 반대로 고려해주었다.