[프로그래머스] level2 12952 - N-Queen(Java)

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

접근 방법

Back-tracking으로 탐색한다.

Back-tracking은 DFS(완전탐색)과 가지치기(분기)를 합친 알고리즘을 의미한다.

탐색하는 도중에, 조건에 맞지 않는 경우를 제외시키며 진행하는 원리다.

N-Queens같은 경우는, 현재 놓인 퀸의 위치에 따라 다음 퀸을 놓을 수 있는 지를 판단하며 진행해야 한다.

각 행에 위치한 퀸의 열 위치를 저장(vy[])하며 다음과 같은 조건을 확인한다.

1. 행 위치 확인(따로 코드 x)
2. 열 위치 확인
3. 대각선 위치 확인
   • 대각선 위치 확인은 x좌표의 차이값과 y좌표의 차이값이 같으면 같은 선상에 있다고 볼 수 있다.

        for(int i=1;i<x;i++){
            if(y == vy[i]) return;
            if(Math.abs(x - i) == Math.abs(y - vy[i])) return;
        }

소스 코드

class Solution {

    static int answer = 0;
    static int[] vy = new int[13]; // 1~12

    public int solution(int n) {
        for(int i=1;i<=n;i++){
            go(1, i, n);
        }
        return answer;
    }

    public void go(int x, int y, int n){
        // 1. 행 위치 확인(따로 코드 x)
        // 2. 열 위치 확인
        // 3. 대각선 위치 확인
        for(int i=1;i<x;i++){
            if(y == vy[i]) return;
            if(Math.abs(x - i) == Math.abs(y - vy[i])) return;
        }

        // 종료 조건
        if(x == n){
            answer++;
            return;
        }

        vy[x] = y; // x행의 y값 저장

        for(int i=1;i<=n;i++){
            go(x+1, i, n);
        }
    }
}