[백준] K-Queen 26006 : Java

1. 문제

https://www.acmicpc.net/problem/26006

 

 

2. 접근

모든 퀸 들을 순회하면서 공격 가능한 지역을 체크하는건가? 했으나 N의 크기가 엄청 크기 때문에 맵에다 표시를 남기는 것은 아니라고 생각했다. 그러면 킹의 좌표와 퀸의 좌표만 가지고 바로바로 공격 가능한 지역에 있는지 확인하기로 했다.

 

공격 가능한 지역을 문제에 나온대로 따져보면 3가지가 나온다.

1. 행이 같을 때

2. 열이 같을 때

3. 대각선이 같을 때

 

이는 각 코드로 다음과 같이 표현할 수 있다. 킹의 인접 칸 중 저 로직에 해당하는 것이 있으면 거긴 공격 가능한 지역인 것이다. 

    public static boolean isAttack(int kingR, int kingC, int queenR, int queenC){
        if(kingR == queenR){
            return true;
        }
        if(kingC == queenC){
            return true;
        }
        if(Math.abs(kingR -queenR)  == Math.abs(kingC-queenC)){
            return true;
        }
        return false;
    }

 

 

이제 킹의 주변 위치들을 순회하면서 해당 칸이 공격가능한 지역인지 확인한다.

int [] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
int [] dc = {0, 1, 1, 1, 0, -1, -1, -1};

int attackCount = 0;
for(int d=0; d<dr.length; d++){
    int nr = king[0] + dr[d];
    int nc = king[1] + dc[d];

    // 범위를 벗어난 경우 판단을 위해 공격 카운팅을 증가시킴
    if(nr <1 || nr >N || nc <1 || nc >N){
        attackCount++;
        continue;
    }

    for(int [] queen : queens){
        if(isAttack(nr, nc, queen[0], queen[1])){
            attackCount++;
            break;
        }
    }
}

만약 공격 가능 지역이라면 attackCount에 1를 더한다. attackCount가 8이면 킹이 어떻게 움직여도 다음에 공격을 받는 것을 나타낸다. 이때 중요한 것은 범위를 벗어난 지역이면 attackCount에 1를 더하는 것이다. 왜냐하면 CHECK와 CHECKMATE의 기준을 attackCount가 8이냐 아니냐로 삼았기 때문이다.

 

 

마지막으로 출력값을 구해야 한다.

if(isAttacking){
    if(attackCount == 8){
        System.out.println("CHECKMATE");
    }
    else{
        System.out.println("CHECK");
    }
}
else{
    if(attackCount == 8){
        System.out.println("STALEMATE");
    }
    else{
        System.out.println("NONE");
    }
}

우선 킹의 현재 칸이 공격이 가능한지에 따라 CEHCK, CHECKMATE / STALEMATE, NONE으로 나눈다. 그리고 주변 인접칸(8칸)이 모두 공격 가능 한지에 따라 각 분기를 나눠준다. 

 

 

3. 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;


public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, K;
    static List<int[]> queens = new ArrayList<>();
    static int[] king;
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c= Integer.parseInt(st.nextToken());
        king = new int[]{r, c};

        for(int i=0; i<K; i++){
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            queens.add(new int[]{r,c});
        } // 입력 끝


        int [] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
        int [] dc = {0, 1, 1, 1, 0, -1, -1, -1};

        int attackCount = 0;
        for(int d=0; d<dr.length; d++){
            int nr = king[0] + dr[d];
            int nc = king[1] + dc[d];

            // 범위를 벗어난 경우 판단을 위해 공격 카운팅을 증가시킴
            if(nr <1 || nr >N || nc <1 || nc >N){
                attackCount++;
                continue;
            }

            for(int [] queen : queens){
                if(isAttack(nr, nc, queen[0], queen[1])){
                    attackCount++;
                    break;
                }
            }
        }

        // 현재 공격받고 있는지 확인
        boolean isAttacking = false;
        for(int [] queen : queens){
            if(isAttack(king[0], king[1], queen[0], queen[1])){
                isAttacking = true;
                break;
            }
        }

        if(isAttacking){
            if(attackCount == 8){
                System.out.println("CHECKMATE");
            }
            else{
                System.out.println("CHECK");
            }
        }
        else{
            if(attackCount == 8){
                System.out.println("STALEMATE");
            }
            else{
                System.out.println("NONE");
            }
        }
    }

    public static boolean isAttack(int kingR, int kingC, int queenR, int queenC){
        if(kingR == queenR){
            return true;
        }
        if(kingC == queenC){
            return true;
        }
        if(Math.abs(kingR -queenR)  == Math.abs(kingC-queenC)){
            return true;
        }
        return false;
    }

}