[백준] 9663 N-Queen - 자바

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

9663번: N-Queen

문제 풀이

이 문제를 보고 백트래킹으로 이용하여 어떻게 구현해야 할지 감은 왔지만 막상 코딩하다 보니 막히던 곳이 해당 좌표에 퀸을 놓을 때 놓을 수 있는 자리인가?를 구하는 거였다. 당연히 행과 열에 대해선 겹치는 부분을 쉽게 구할 수 있지만 대각선이 겹치는 걸 어떻게 판별해야 할까?

 

이 부분을 해결하기 위해 각 행에 몇 번째 열에 퀸이 있는지를 기록해야 한다. 이 값들이 있으면 대각선의 존재 유무를 쉽게 확인할 수 있다.

현재 좌표와 위에서 저정돤 퀸의 좌표에서 행의 차이 == 열의 차이가 같다면 대각선 상에 존재한다.

if (abs(row - col) == abs(queenCol[row] - queenCol[col]))
	...

 

또 중요한 포인트 하나가 N*N 행렬에 대해서 위에서 언급한 '각 행에 몇 번째 열에 퀸이 있는지를 기록' 을 위해 N*N 좌표를 선언할 필요가 없다. 생각해보면 각 행에 대해서 각 열은 하나만 존재하기 때문에 1차원 배열로 충분하다.

 

코드를 살펴보자

코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Math.*;

public class b9663 {
    static int[] queenCol;
    static int n;
    static int cnt = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        queenCol = new int[n];
        dfs(0);
        System.out.println(cnt);
    }

    static void dfs(int row) {
        if (row == n) {
            cnt++;
            return;
        }
        for (int col = 0; col < n; col++) {
            queenCol[row] = col;
            if (canQueen(row))
                dfs(row+1);
            }    
    }

    static boolean canQueen(int row) {
        for (int col = 0; col < row; col++)
        	// 같은 열이거나 대각선 상에 존재한다면
            if (queenCol[row] == queenCol[col]
                    || abs(row - col) == abs(queenCol[row] - queenCol[col]))
                return false;

        return true;
    }
}

느낀점

접근하는법은 감을 잡았으나 대각선 판별에서 막힌 문제다. 막상 알고 푸니 크게 어려운 문제는 아닌 것 같다.