프로그래머스 Lv.3) N-Queen

N-Queen

코딩테스트 연습 - N-Queen

풀이

체스 규칙을 알고있는데, 처음 코드를 짤 때 전체 대각선을 확인하지 않아서 한번의 수정을 거쳐 풀었다.

처음에는 1차원 배열인 visit을 남겨 각 column마다 방문 여부만 저장하고, 방문하지 않은 곳과 바로 위의 퀸과 위치 비교만 했다. 위치 비교는 좌상단, 상단, 우상단 세 부분만 체크를 했고, 결과적으로 40점이 나왔다.

 

행 = 세로, column

열 = 가로, row

 

틀렸다는 것을 확인하고 나서야, 대각선 확인에 대해 생각이 들었고 visit 배열을 어떤 row(열)에 queen을 배치했는지 저장하는 방식으로 바꿔주었다.

행 단위로 메소드가 진행되고, 0행부터 N까지 column마다 퀸을 재귀로 넣어준다.

각 row(열)를 돌면서 배치한 열이 아니면 queen을 배치할 수 있는지 확인하고, 만들 수 있다면 visit의 row(= index)에 재귀에 들어와 있는 column(행)을 저장한 뒤에 다음 column의 퀸 위치를 확인해줬다.

 

가로, 세로, 대각선을 확인해야하지만 어차피 column를 재귀를 통해 순차적으로 돌고있고(세로 판단할 필요 없음),

특정 row에 퀸이 배치된 column을 저장(가로 판단할 필요 없음)해주기 때문에 가로 세로는 확인하지 않았다. (알아서 검증되기 때문)

 

대각선을 확인하는 방식은 간단하다. 퀸이 들어갈 수 있는지 입력받은 위치에서, 이미 퀸이 배치되어 있는 곳들과 순차적으로 확인을 해주면 된다. 확인은 두 좌표의 x축과 y축 각각 차이가 같은 곳인지만 보면 된다.

 

예를 들면, (1,1)과 (3,3)은 x축 (3-1 =) 2 차이, y축 (3-1 =) 2 차이가 나기 때문에 대각선이다.

반면에 (1,1)과 (3,2)는 x축 (3-1 =) 2 차이, y축 (3-2 =) 1 차이가 나기 때문에 대각선이 아니다.

좌표를 그려서 여러 점을 확인해보면 명확해질 겁니다.

 

로직

1. 재귀 메소드 makeQueen을 만들고, 행마다 for문을 통해 열을 탐색한다.

 1-1. 해당 열(row)에, 어떠한 행(col)에도 저장되어 있지 않다면, isPossible 메소드를 통해 대각선을 확인해준다. 

 1-2. 첫번째 행인 경우는 true를 반환해준다. (어떠한 위치도 가능)

 1-3. 이전 행들에 저장되어 있는 퀸들과 대각선인지 판단한다.

 1-4. 대각선 판단은 x축과 y축 각각의 차이가 같은지로 확인한다.

2. 퀸을 배치할 수 있는 곳이면, 해당 열에 행을 저장해주고, 다음 행에 대해 재귀 탐색을 시작한다.

 

코테 볼때는 점수를 가르쳐주지 않으니까 조금 더 집중하자 !!!

 

코드

class Solution {
    int answer;
    public int solution(int n) {
        answer = 0;
        makeQueen(new int[n+1], 1);
        System.out.println(answer);
        return answer;
    }
    
    private void makeQueen(int visit[], int row) {
        if(row ==visit.length) { // 되는 경우
            answer++;
            return;
        }
        
        for(int i=1; i<visit.length; i++) {
            if(visit[i] ==0) {  // 배치한 열이 아니면(가로)
                if(isPossible(row, visit, i)) {
                    visit[i] =row;  // 저장한 세로 행을 넣어줌
                    makeQueen(visit, row+1);
                    visit[i] =0;    // 초기화
                }
            }
        }
    }
    private boolean isPossible(int row, int[] visit, int col) {
        boolean result = true;
        if(row > 1) {   // 첫번째 행은 다 배치 가능
            for(int i=1; i<visit.length; i++) {  // col 탐색
                int origin = visit[i];  // row
                if(origin !=0) { // 이미 퀸 배치한 곳만 검사
                    if(Math.abs(i-col) == Math.abs(row-origin)) {   // 대각선 검증
                        result = false;
                        break;
                    }
                }
            }
        }
        return result;
    }
}