[BOJ] 17135. 캐슬디펜스 - Java

Java 알고리즘을 처음 연습하는 과정에서 어려움을 겪은 문제이다. 나는 해당 문제는 조합과 시뮬레이션을 함께 사용해서 풀었다. 어려움을 겪었던 부분이 몇 가지 있고, 알게 된 내용이 있다.

오류를 해결했던 부분

1. 전체 맵을 계속 복사할 temp[] 배열에서 적을 없애는 과정을 하지 않아서 제대로 된 답이 나오지 않았었다.

2. 중복으로 적을 공격해도 된다는 제약사항으로 HashSet 컬렉션을 사용했는데, 처음에 HashSet<int[]> 를 사용하여 중복 제거가 제대로 이루어지지 않았던 것 같다. 이를 통해 클래스를 만들어 hashCode()와 equals() 메서드를 이용하여 중복체크 하는 부분을 공부하게 되었다.

   → 해당 과정에서, static 메서드 안에서 클래스를 사용하려면 static class를 만들어주어야 한다는 내용을 누락하여 디버깅 하여 찾았고, 다음부터 실수하지 않을 수 있을 것 같다!

문제 해결 과정

조합은 재귀적으로도 할 수 있지만, 해당 문제에서는 조합의 경우가 정해져 있기에 3중 for문을 이용하여 간단하게 조합을 구현하였고, 시뮬레이션을 제대로 따져 구현하였다. 해당 코드는 디버깅 한 코드까지 주석처리 하여 같이 담은 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.StringTokenizer;

public class BOJ_17135_캐슬디펜스 {

    static int N, M, D;
    static int[][] map = new int[17][17];
    static int[][] temp = new int[17][17];
    static int answer = Integer.MIN_VALUE;
    static ArrayList<RC> enemies = new ArrayList<>();
    static HashSet<RC> finishEnemies = new HashSet<>();
    static HashSet<RC> tempEnemies = new HashSet<>();

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

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(in.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(in.readLine(), " ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    enemies.add(new RC(i, j));
                }
            }
        }

        mC3();

        System.out.println(answer);
    }

    private static void mC3() {
        int n = N;
        for (int i = 0; i < M; i++) {
            for (int j = i + 1; j < M; j++) {
                for (int k = j + 1; k < M; k++) {
                    check(n, i, j, k);
                }
            }
        }
    }

    private static void check(int n, int i, int j, int k) {
        initTemp();
        finishEnemies.clear();
//        System.out.println(i+" "+j+" "+k+" start");

        while (true) {
            if (n == 0)
                break;
            tempEnemies.clear();

            startBow(n, i);
            startBow(n, j);
            startBow(n, k);

            Iterator<RC> iter = tempEnemies.iterator();

            while (iter.hasNext()) {
                RC deleteTemp = iter.next();
//                System.out.println(deleteTemp.r+ " " + deleteTemp.c);
                temp[deleteTemp.r][deleteTemp.c] = 0;
            }
//            System.out.println();
            --n;
        }

        answer = Math.max(answer, finishEnemies.size());
    }

    private static void startBow(int n, int bowC) {
        int minDist = Integer.MAX_VALUE;
        int minR = -1;
        int minC = -1;
        for (RC enemy : enemies) {
            if (enemy.r >= n - D && enemy.r < n) {
                if(temp[enemy.r][enemy.c] != 1) continue;
                int dist = Math.abs(n - enemy.r) + Math.abs(bowC - enemy.c);
                if (dist <= D) {
                    if (minDist > dist) {
                        minDist = dist;
                        minR = enemy.r;
                        minC = enemy.c;
                    } else if (minDist == dist && enemy.c < minC) {
                        minR = enemy.r;
                        minC = enemy.c;
                    }
                }
            }
        }
        if (minDist != Integer.MAX_VALUE) {
            finishEnemies.add(new RC(minR, minC));
            tempEnemies.add(new RC(minR, minC));
        }
    }

    private static void initTemp() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                temp[i][j] = map[i][j];
            }
        }
    }

    public static class RC {
        int r;
        int c;

        public RC(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }

        public RC() {
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + c;
            result = prime * result + r;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            RC rc = (RC) obj;
            if (rc.r == this.r && rc.c == this.c) {
                return true;
            } else {
                return false;
            }
        }
    }
}