Don't give up!

[프로그래머스] N-Queen (java) 본문

Coding Test/Programmers

[프로그래머스] N-Queen (java)

Heang Lee 2021. 6. 23. 13:05

코딩테스트 연습 - N-Queen | 프로그래머스 (programmers.co.kr)

 

코딩테스트 연습 - N-Queen

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은

programmers.co.kr

어떻게 생각하고 문제를 풀었는가?

체스판의 크기 N이 12이하의 자연수이므로 가능한 모든 경우를 직접 확인하여 카운트하고자 하였습니다.

1번째 줄부터 k-1번째 줄까지 진행하면서 퀸을 배치하고, 모든 퀸을 배치했을 때 이를 카운트, 다른 열에 배치한 경우에 대해서도 이를 수행함으로써 문제를 해결할 수 있습니다.

코드

import java.util.*;
class Solution {
    int[] rows;
    public int solution(int n) {
        rows = new int[n];
        return countCases(0,n);
    }
    int countCases(int k,int n){
        if(k==n)    return 1;
        int count = 0 ;
        for(int i=0; i<n; i++){
            if(allowed(i,k)){
                rows[k] = i;
                count += countCases(k+1,n);
            }
        }
        return count;
    }
    boolean allowed(int i, int k){
        for(int j=0; j<k; j++){
            if(rows[j]==i || k-j == Math.abs(i-rows[j])) return false;
        }
        return true;
    }
}

k번째 줄에 퀸을 배치할 때 배치가능한 열은 k-1번째 줄까지 배치된 퀸들과 직선, 대각선으로 겹치지 않아야 합니다.

각 줄에 대해 반복문을 수행하므로 열에 대한 중복, 대각에 대한 중복만 체크하면 되며 두 퀸이 대각선에 있는지 확인하는 방법은 x좌표의 차와 y좌표의 차를 비교하여 확인할 수 있습니다.

가능한 모든 열을 확인하고 재귀함수를 호출함을 통해 모든 케이스를 카운트하여 답을 구할 수 있습니다.