[랜덤 마라톤] 더 푸르게(9983)

1. 문제 풀이 아이디어

• 비트마스킹을 활용한 브루트포스 탐색으로 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    static int[][] king = {{0, 1}, {1, 1}, {0, -1}, {1, -1}, {1, 0}, {-1, 1}, {-1, 0}, {-1, -1}};
    static int[][] knight = {{2, 1}, {1, 2}, {1, -2}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};
    static int h;
    static int w;
    static String[][] sBoard;
    static int[][] pieces = new int[16][2];
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        String line;
        while ((line = bufferedReader.readLine()) != null) {
            if (!line.equals("START"))
                break;
            w = Integer.parseInt(bufferedReader.readLine());
            h = Integer.parseInt(bufferedReader.readLine());
            sBoard = new String[h][];
            count = 0;
            for (int i = 0; i < h; i++) {
                line = bufferedReader.readLine();
                sBoard[i] = line.split(" ");
                for (int j = 0; j < w; j++) {
                    if (sBoard[i][j].equals("E"))
                        continue;
                    pieces[count][0] = i;
                    pieces[count][1] = j;
                    count++;
                }
            }
            int result = count;
            for (int i = 0; i < (1 << count); i++) {
                if (solve(i)) {
                    result = Math.min(result, count - Integer.bitCount(i));
                }
            }
            stringBuilder.append("Minimum Number of Pieces to be removed: ").append(result).append('\n');
            line = bufferedReader.readLine();
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }

    static boolean inBoard(int x, int y) {
        return (x >= 0 && y >= 0 && x < h && y < w);
    }

    static boolean check(int x, int y, String piece, boolean[][] bBoard) {
        if (piece.equals("K") || piece.equals("N")) {
            int[][] moves = (piece.equals("K")) ? king : knight;

            for (int i = 0; i < 8; i++) {
                int nx = moves[i][0] + x;
                int ny = moves[i][1] + y;
                if (inBoard(nx, ny) && bBoard[nx][ny]) return false;
            }
        } else {
            int[][] moves = king;
            int steps = 10;

            for (int i = 1; i <= steps; i++) {
                for (int j = (piece.equals("B") ? 1 : 0); j < 8; j += (piece.equals("Q") ? 1 : 2)) {
                    int nx = moves[j][0] * i + x;
                    int ny = moves[j][1] * i + y;
                    if (inBoard(nx, ny) && bBoard[nx][ny]) return false;
                }
            }
        }
        return true;
    }

    static boolean solve(int mask) {
        boolean[][] bBoard = new boolean[10][10];

        for (int i = 0; i < count; i++) {
            if ((mask & (1 << i)) != 0) {
                bBoard[pieces[i][0]][pieces[i][1]] = true;
            }
        }

        for (int i = 0; i < count; i++) {
            if ((mask & (1 << i)) == 0) continue;

            int x = pieces[i][0];
            int y = pieces[i][1];
            String piece = sBoard[x][y];

            if (!check(x, y, piece, bBoard)) {
                return false;
            }
        }
        return true;
    }
}

3. 정리

• 말의 위치를 배열 pieces에 저장하며, 말의 수를 count로 관리한다.

• 모든 말의 상태를 비트마스크로 표현하여 0이면 제거된 상태, 1이면 남아있는 상태로 관리한다.

• 이를 활용하여 for문을 순회하며 solve 메서드를 통해 문제의 조건이 맞는지 확인한다.

• solve 메서드
• 비트마스크를 기반으로 현재 체스판의 상태(bBoard)를 생성한다.
• 각 말의 위치와 유형(킹, 나이트, 퀸, 비숍)을 확인하여, check 메서드를 사용해 해당 말이 공격 가능한 위치를 검사한다.
• 모든 말이 서로 공격하지 않으면 true를 반환한다.

• check 메서드
• 입력된 말의 유형에 따라 이동 가능한 패턴(king, knight)을 설정하거나 퀸, 비숍의 경우 직선 이동을 고려한다.
• 설정된 이동 패턴을 기반으로 공격 가능한 위치를 검사하고, 공격 범위 내에 다른 말이 있으면 false를 반환한다.

• 모든 비트마스크 상태를 탐색하며, 서로 공격하지 않도록 만드는 데 필요한 최소 제거 횟수를 계산하여 문제를 해결한다.