[프로그래머스/Lv. 2] N-Queen (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 백트래킹

필요 자료구조
- 1차원 int형 배열 (퀸의 위치 나타냄) ⭐
- 갯수 저장할 1차원 int형 변수

arr[i] = j : (i, j) 위치에 퀸을 둔다는 의미의 배열

- 퀸, 상하좌우 및 대각선으로 거리 제한 없이 한 방향으로 이동 가능하며,  이 이동가능한 동선과 겹치지 않는 곳에 또 다른 퀸을 배치해야 함

- 각 행 별로 놓을 수 있는 위치에 있을 때 재귀호출하고, 만약 모두 배치되었다면 count하면서 경우의 수 찾아냄

  > 놓을 수 있는 위치인지 확인

      → 1) 같은 열에 존재하는지 확인하기

      → 2) 같은 대각선 상에 존재하는지 확인하기

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int n;
    static int answer = 0;
    static int[] arr;   // arr[i] = j : (i,j)에 퀸을 둔다는 의미의 배열
    
    public int solution(int n) {
        this.n = n;
        arr = new int[n];
        
        nQueen(0);        
        return answer;
    }
    
    private static void nQueen(int row) {
        if (row == n) { // 행 다 채우면, 정답 +1하고 리턴
            answer++;
            return;
        }
                
        for (int i = 0; i < n; i++) {
            arr[row] = i;   // 🔔 (row, i) 위치에 퀸 둔다는 의미
            
            if(isValid(row)) {   // 놓을 수 있는 위치라면, 재귀 호출
                nQueen(row + 1);
            }
        }
    }
    
    // 놓을 수 있는 위치인지 판별하는 함수 (→ 열, 대각선 확인)
    private static boolean isValid(int col) {
        for(int i = 0 ; i < col ; i++) {
            if(arr[col] == arr[i])  // 1) 같은 열에 존재하면 안 됨
                return false;
 
            if(Math.abs(col - i) == Math.abs(arr[col] - arr[i]))    // 2) 같은 대각선 상에 놓이면 안 됨
                return false;
        }
        
        return true;
    }
}
 

 

 

 

➕ 다른 풀이 방식

- 깔끔한 설명!

프로그래머스 - N Queen(Java)

 

[프로그래머스 , 자바] Level2: N-Queen

---

💦 어려웠던 점

- 1차원 배열의 의미를 제대로 파악하지 못 하였다..

 

 

🧐 새로 알게 된 내용

2차원 배열을 1차원 배열로 압축시키기

- 배열의 idx를 행, 배열의 값을 열로 보기

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준/JAVA] 9663번: N-Queen