[JAVA] 백준 1986 : 체스

[JAVA] 백준 1986 : 체스

문제

주어진 NxM의 체스판에 Knight, Queen, Pawn이 주어질 때, 이 말들을 움직였을 때 잡힐 수 없는 안전한 칸의 개수를 구하는 문제

Knight : 2x3의 직사각 형을 만들 었을 때, 해당 점에서 가장 먼 점으로만 이동할 수 있다. 중간에 다른 말이 있어도 영향을 받지 않는다.

Queen : 가로, 세로, 대각선으로 쭉 움직일 수 있다. 단, 중간에 다른 말이 있다면 그 전까지만 이동할 수 있다.

Pawn : 움직이지 못하고 그저 장애물 역할만 한다.

접근방법

주어진대로 노가다 코드를 짜면 얼마든지 해결할 수 있다.

즉, 먼저 Queen이 갈 수 있는 범위를 체크하고, 그 다음으로 Knight가 갈 수 있는 범위를 체크하고, 해당 말 들이 없는 칸들의 개수를 세서 출력해주면 된다.

1. 먼저 queen, knight의 위치를 ArrayList에 저장하고, char배열인 맵의 해당 위치에 각 말의 알파벳(K, Q, P)을 넣어준다.

2. 각 queen, knight를 정해진 규칙에 따라 이동하도록 하고, 이동한 좌표는 'o'로 바꾸어 준다.

3. 각 말들이 이동하지 않은 곳은 char의 초기값인 '\u0000'이 들어있으므로, 이러한 원소들의 개수를 확인해 출력해준다.

같은 스터디원의 코드를 참고해 더 깔끔하게 코드를 수정해 보았다.

1. dx, dy 배열을 이용하면 규칙이 없더라도 for문으로 돌릴 수 있다.

   • 예를 들어 위, 아래, 오른쪽, 왼쪽, 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래를 확인해야 하는 Queen의 경우에는 dx, dy 배열을 이용해 아래와 같이 코드를 짤 수 있다.

     for(int i=0; i<8; i++){
         int next_x = x;
         int next_y = y;
         while(true) {
             next_x += dx[i];
             next_y += dy[i];
     ​
             if(next_x < 0 || next_x >= N || next_y < 0 || next_y >= M)
                 break;  // map 범위를 벗어나는 경우
             if(map[next_x][next_y] == 'K'
                     || map[next_x][next_y] == 'Q'
                     || map[next_x][next_y] == 'P' )
                 break;  // 말이 지나갈 수 없는 경우(K/P/Q)
     ​
             map[next_x][next_y] = 'o';
         }
     }

   • knight의 움직임 경우에는 아래와 같이 코드를 짤 수 있다.

     int[] dx = {2, 2, 1, 1, -1, -1, -2, -2};
     int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};
     ​
     for(int i=0; i<8; i++){
         int next_x = x + dx[i];
         int next_y = y + dy[i];
     ​
         if(next_x >= 0 && next_x < N
                 && next_y >=0 && next_y < M){   // 배열 범위 내에 있으면서
             if(map[next_x][next_y] == '\u0000') // 빈칸일 경우
                 map[next_x][next_y] = 'o';
         }
     }

소스코드

    static int N, M;
    static char[][] map;
​
    static class Pos{
        int x; int y;
        public Pos(int x, int y) {this.x = x; this.y = y;}
    }
​
    static void checkQueen(int x, int y){
​
        int[] dx = {1, -1, 0, 0, 1, 1, -1, -1};
        int[] dy = {0, 0, 1, -1, 1, -1, 1, -1};
​
        for(int i=0; i<8; i++){
            int next_x = x;
            int next_y = y;
            while(true) {
                next_x += dx[i];
                next_y += dy[i];
​
                if(next_x < 0 || next_x >= N || next_y < 0 || next_y >= M)
                    break;  // map 범위를 벗어나는 경우
                if(map[next_x][next_y] == 'K'
                        || map[next_x][next_y] == 'Q'
                        || map[next_x][next_y] == 'P' )
                    break;  // 말이 지나갈 수 없는 경우(K/P/Q)
​
                map[next_x][next_y] = 'o';
            }
        }
    }
​
    static void checkKnight(int x, int y){
        int[] dx = {2, 2, 1, 1, -1, -1, -2, -2};
        int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};
​
        for(int i=0; i<8; i++){
            int next_x = x + dx[i];
            int next_y = y + dy[i];
​
            if(next_x >= 0 && next_x < N
                    && next_y >=0 && next_y < M){   // 배열 범위 내에 있으면서
                if(map[next_x][next_y] == '\u0000') // 빈칸일 경우
                    map[next_x][next_y] = 'o';
            }
        }
    }
​
    public static void main(String[] args) throws IOException{
​
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
​
        String[] input = in.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
​
        map = new char[N][M];
​
        ArrayList<Pos> queen = new ArrayList<>();
        ArrayList<Pos> knight = new ArrayList<>();
​
        // input
        for(int i=0; i<3; i++){
            input = in.readLine().split(" ");
            int num = Integer.parseInt(input[0]);
​
            for(int j=1; j<=num; j++){
                int x = Integer.parseInt(input[2*j-1]) - 1;
                int y = Integer.parseInt(input[2*j]) - 1;
​
                if(i==0){
                    queen.add(new Pos(x,y));
                    map[x][y] = 'Q';
                }else if(i==1){
                    knight.add(new Pos(x,y));
                    map[x][y] = 'K';
                }else{
                    map[x][y] = 'P';
                }
            }
        }
​
        // queen check
        for(int i=0; i<queen.size(); i++)
            checkQueen(queen.get(i).x, queen.get(i).y);
​
​
        // knight check
        for(int i=0; i<knight.size(); i++)
            checkKnight(knight.get(i).x, knight.get(i).y);
​
        int answer = 0;
        for(int i=0; i<N; i++)
            for(int j=0; j< M; j++)
                if(map[i][j] == '\u0000')
                    ++answer;
​
        System.out.println(answer);
    }