[프로그래머스 level_3] N-Queen for JAVA

https://programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

[문제 설명]

 

가로, 세로 길이가 n인 정사각형으로 된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한 번에 공격할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

 

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

---

입출력 예

n	result
4	2

 

[풀이]

• "퀸은 가로, 세로, 대각선으로 공격할 수 있다"라는 말은 체스판에서 하나의 퀸에 해당하는 열과 행, 대각선 등이 비어있어야 한다는 것을 뜻함.
• n의 숫자가 크지 않으므로 재귀함수를 사용해도 됨.
• 열에 해당하는 배열에는 몇 번째 자리에 퀸이 배치됐는지 표현
• 행에 해당하는 배열에는 그 행이 지금 퀸이 있는지 없는지를 표현
• 대각선은 오른쪽 위에서 왼쪽 아래로, 왼쪽 위에서 오른쪽 아래로 오는 배열 선언 <- 중요

n=5인 체스판

조건에 해당하는 하나의 체스판 예시

• 열에 해당하는 배열에는 [1,3,1,2,4]가 들어가 있을 것이고
• 행에 해당하는 배열은 [true, true, true, true, true]가 되어있을 것이다.
• 대각선 배열도 마찬가지로 모두가 true

- 우리는 대각선이 채워져 있는지 없는지를 판단하는 배열을 만들어야 하는데 처음부터 끝까지 대각선으로 탐색하는 건 구현도 어렵고 시간도 오래 걸린다. 하나의 규칙을 찾아보자.

j와i의 인덱스를 더한 체스판

 

-우리는 여기서 오른쪽 위에서 왼쪽 아래로 내려오는 대각선의 규칙을 찾을 수 있다. 즉, 

손재주가 없습니다.. 보는분들에겐 죄송합니다..

- 오른쪽 위에서 왼쪽 아래로 내려오는 대각선의 규칙은 체스판[i+j] = false, true로 나눠질 수 있을 것이다.

- ex) i = 0, j = 0 -> 체스판[0] = true -> 0열, 0행의 대각선은 이미 꽉 차 있다.

- ex) i = 4, j = 2 -> 체스판[6] = false -> 체스판에 안에 6이 차있는 대각선은 비어있다.

- 왼쪽 위에서 오른쪽 아래로 내려오는 대각선의 규칙을 찾아보자.

다시 한번 미안합니다..

- 바로 예를 들어보자 i=1, j=4와 i=0, j=3인 부분이 같은 대각선 라인에 있다 규칙은 i - j + (n-1) 같다.

- 이렇게 되면 저기 0부터 8, 즉 n*2 -1의 크기에 해당하는 boolean배열이 이 대각선들의 사용 가능/불가능을 파악할 수 있다.

 

자세한 건 코드의 전체적인 흐름을 보며 이해해보자!

 

[코드]

public class NQueen {
    int count;
    boolean[] checkRow;           // 행 중복검사
    boolean[] checkDiagonalR;  // \방향 대각선
    boolean[] checkDiagonalL;  // /방향 대각선
    int[] answer;               // 각 열에 해당하는 퀸의 위치
     public int solution(int n) {
        answer = new int[n];
        checkRow = new boolean[n];
        checkDiagonalL = new boolean[n *2 -1];
        checkDiagonalR = new boolean[n *2 -1];
        count = 0;
        set(0, n);
        
        return count;
        
    }
    public void set(int i, int n) {
        for(int j = 0; j < n; j++) {
            if(!checkRow[j] && !checkDiagonalL[i+j] && !checkDiagonalR[i-j+n-1]) { //행이 비었고, 왼쪽, 오른쪽 대각선의 조건에 만족할 시.
                answer[i] = j;
                if(i == n-1) {
                    count++;
                    return;
                }else {
                    checkRow[j] = checkDiagonalL[i+j] = checkDiagonalR[i-j+n-1] = true;
                    set(i+1, n);
                    checkRow[j] = checkDiagonalL[i+j] = checkDiagonalR[i-j+n-1] = false;
                }
            }
        }
    }

프로그래머스 테스트 케이스 통과

느낀 점 : Queen문제를 처음 풀어본다. 글씨로 적고 구상을 해봐도 잘 안 풀리길래 예전에 사놓았던 책을 보며 공부해서 머릿속에 담고 혼자 문제를 풀어봤다. 이해가 잘 된 것 같아서 좋다.