[자바] 백준 10469 - 사이 나쁜 여왕들 (boj java)

문제 : boj10469

 

  '*'이 나온 모든 위치에서 상하좌우, 대각선으로 퀸이 없으면 valid, 있다면 invalid인 간단한 구현 문제이다. 매번 '*' 위치에서 판의 끝까지 위,아래,좌우,대각선으로 탐색하면서 '*'이 있는지 확인하면 풀 수 있다. 

  하지만 그냥 매번 '*'의 위치에서 brute force로 직접 탐색하며 확인하긴 심심하니 난 내 수준에서 생각할 수 있는 가장 간단하게(짧게) 찾는 방법을 사용해 풀어봤다. 설명은 코드에 주석으로 달아두었다.

 

  그리고 맞왜틀 나기 아주 좋은 함정이 있다. '사이나쁜 여왕 퀴즈는 여덟 여왕을 8x8 체스판 위에 배치' 여덟 여왕이랬으므로 '*'의 개수가 8개가 아니면 invalid이다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    ArrayList<int[]> queen;
    int rowCnt, colCnt;
    private boolean chk(int i, int j) {
        // 세로 체크 (i가 2였다면 세로에서 처음 나온거라면 ..00000 -> ..00100, 두번째는 ..00100 -> ..00000 이 되므로 1<<i가 0이 됨.)
        if (((rowCnt^=1<<i)&1<<i)==0) return false;
        // 가로 체크 (위와 동일)
        if (((colCnt^=1<<j)&1<<j)==0) return false;
        // 대각선 체크 (x, y축 각각의 차이의 절대값이 동일하면 대각선 위치임)
        for (int k = 0; k < queen.size(); k++) {
            if (Math.abs(queen.get(k)[0]-i) == Math.abs(queen.get(k)[1]-j))
                return false;
        }
        queen.add(new int[]{i, j});
        return true;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        queen = new ArrayList<>();
        int cnt = 0;
        for (int i = 0; i < 8; i++) {
            String s = br.readLine();
            for (int j = 0; j < 8; j++) {
                if (s.charAt(j) != '*') continue;
                cnt++;
                if (!chk(i, j)) {
                    System.out.println("invalid");
                    return;
                }
            }
        }
        System.out.println(cnt==8?"valid":"invalid");
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}