[programmers] N-Queen

16 Apr 2023 in Algorithm on Algorithm

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

tip. 대각선 움직임은 한 번 움직일 때마다 “행(row)”과 “열(col)”이 동시에 변한다.
✅ 예를 들어 보자
(2, 3) 위치에 퀸이 있다고 해보자.
이 퀸이 대각선으로 움직일 수 있는 위치는 어디일까?
↘ 방향: (3, 4), (4, 5), (5, 6) …
↙ 방향: (3, 2), (4, 1), (5, 0) …
↖ 방향: (1, 2), (0, 1) …
↗ 방향: (1, 4), (0, 5) …

공통점?
→ 전부 row와 col이 같은 양만큼 변하고 있다.
(2, 3) → (3, 4) → row+1, col+1
(2, 3) → (1, 2) → row–1, col–1
(2, 3) → (3, 2) → row+1, col–1

즉, 어느 방향이든 간에
행과 열의 변화량이 똑같다 → 대각선이다.
그래서 |r1 - r2| == |c1 - c2| 면 두 점은 대각선에 있음

class Solution {
    private int answer = 0;

    public int solution(int n) {
        int[] board = new int[n]; // board[i] = i번째 행에 놓은 퀸의 열 위치
        backtrack(board, 0, n);   // 백트래킹 시작
        return answer;
    }

    private void backtrack(int[] board, int row, int n) {
        if (row == n) { // 모든 퀸을 놓았으면 정답 카운트
            answer++;
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col)) { // 조건 만족할 때만 재귀 진행
                board[row] = col;          // 현재 행에 퀸 놓기
                backtrack(board, row + 1, n); // 다음 행으로
            }
        }
    }

    private boolean isSafe(int[] board, int row, int col) {
        for (int prevRow = 0; prevRow < row; prevRow++) {
            int prevCol = board[prevRow];
            if (prevCol == col || Math.abs(prevCol - col) == Math.abs(prevRow - row)) {
                return false;
            }
        }
        return true;
    }
}