[프로그래머스] N-Queen - Java

문제

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

프로그래머스

 

---

 

문제 개요

이 문제는 N-Queens 문제로, 체스판 위에 n개의 퀸을 배치할 때 서로 공격할 수 없도록 하는 방법의 수를 찾는 문제입니다. 퀸은 체스판에서 가로, 세로, 대각선으로 이동할 수 있기 때문에 서로를 공격할 수 없는 위치에 놓는 것이 중요합니다.

 

접근 방법

이 문제는 백트래킹(Backtracking) 기법을 사용하여 해결할 수 있습니다. 백트래킹은 해를 찾는 과정에서 불가능한 경로는 더 깊이 탐색하지 않고 가지를 치는 방식입니다.

알고리즘 설명:

1. 재귀 함수(back):
   • row는 현재 배치할 행을 의미합니다.
   • n이 row와 같아지면 모든 퀸을 배치한 경우이므로 가능한 방법의 수를 증가시킵니다.
2. 퀸 배치:
   • 각 행마다 가능한 모든 열에 퀸을 놓아봅니다.
   • 퀸을 놓을 때는 check 함수로 현재 배치가 유효한지 확인합니다.
3. 체크 함수(check):
   • 현재 행(row)에 놓은 퀸이 이전 행들에 있는 퀸과 같은 열에 있거나, 대각선 위치에 있으면 false를 반환합니다.
   • 퀸이 서로 공격할 수 없는 경우 true를 반환합니다.

코드 설명

• arr 배열은 각 행에 퀸이 놓인 열의 위치를 저장합니다.
• back(n, 0)은 첫 번째 행부터 시작해 재귀적으로 퀸을 배치합니다.
• check(row)는 현재 row에 놓인 퀸이 이전 행에 놓인 퀸과 충돌하지 않는지 확인합니다.
• Math.abs(row - i) == Math.abs(arr[row] - arr[i])는 대각선 충돌을 검사하는 조건입니다. (대각선의 경우 행과 열의 차이가 같으면 충돌합니다)

import java.util.*;
class Solution {
    static int[] arr;
    static int cnt = 0;
    public int solution(int n) {
        int answer = 0;
        arr = new int[n];
        back(n ,0);
        answer = cnt;
        return answer;
    }
    
    static void back(int n, int row) {
        if(n == row) {
            cnt++;
            return;
        }
        for (int i = 0; i < n; i++) {
            arr[row] = i;
            if(check(row)) {
                back(n ,row + 1);
            }
        }
    }

    static boolean check(int row) {
        for (int i = 0; i < row; i++) {
            if(arr[i] == arr[row]) {
                return false;
            }
            if(Math.abs(row - i) == Math.abs(arr[row] - arr[i])) {
                return false;
            }
        }
        return true;
    }
}