[프로그래머스 Level 2] N-Queen

문제

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

프로그래머스

 

 

풀이

• N x N 체스판 위에 퀸을 N개 놓는 경우의 수를 구한다.
• 이때, 퀸은 서로를 공격할 수 없는 위치에 두어야 한다.
• 퀸은 가로, 세로, 대각선으로 거리에 상관없이 움직일 수 있는 말이다.
• N은 12 이하의 자연수이다.

 

대표적인 백트래킹 문제라고 한다. 이때, 조건은 해당 위치에 퀸을 놓을 수 있는가가 된다.

 

체스판이기 때문에 2차원 배열을 사용해야 할 것 같지만 하나의 행 또는 열에는 하나의 퀸만 위치할 수 있기 때문에 각 행 별로 열의 위치를 담은 int형 1차원 배열로 구현할 수 있다.

 

백트래킹 함수의 매개변수는 depth로 한다. depth는 0부터 N-1행까지 탐색하면서 퀸이 위치한 열의 숫자로 퀸을 놓을 수 있는지 판별한다. depth와 N이 같아지는 순간 모든 조건을 만족하고 체스판에 퀸을 N개 채운 것이므로 count에 1을 더하고 return한다.

public void backTracking(int depth){
    if(depth == N){
        count++;
        return;
    }

    for(int i = 0; i < N; i++){
        board[depth] = i;

        if(queen(depth)){
            backTracking(depth + 1);
        }
    }

}

 

queen이라는 함수는 해당 위치에 퀸을 놓을 수 있는지 판별한다.

0부터 depth까지, 즉 이전 행에 둔 퀸의 위치와 현재 위치를 비교해야 한다. 비교할 포인트는 두가지이다.

1. 같은 열에 위치하는가?
2. 대각선 상에 위치하는가?

같은 열에 위치하는지 판별하는 것은 쉽다. board[이전행] == board[현재행] 이면 false를 return한다.

대각선 상에 위치하는지는 어떻게 판별할까? 대각선은 기울기가 1 또는 -1이다. 즉, 이전 행과 현재 행의 차와 이전 열과 현재 열의 차가 같다는 뜻이다.

public boolean queen(int d){
    for(int i = 0; i < d; i++){
        if(board[i] == board[d])
            return false;

        if(Math.abs(i - d) == Math.abs(board[i] - board[d]))
            return false;
    }

    return true;
}

 

최종적으로 퀸을 둘 수 있는 곳이라고 판별되면 depth + 1 후 다음 backTracking을 시작한다.

 

 

전체 코드 (Java)

import java.util.*;

class Solution {
    static int N;
    static int[] board;
    static int count = 0;
    
    public int solution(int n) {
        board = new int[n];
        N = n;
        
        backTracking(0);
        
        return count;
    }
    
    public void backTracking(int depth){
        if(depth == N){
            count++;
            return;
        }
        
        for(int i = 0; i < N; i++){
            board[depth] = i;
            
            if(queen(depth)){
                backTracking(depth + 1);
            }
        }
        
    }
    
    public boolean queen(int d){
        for(int i = 0; i < d; i++){
            if(board[i] == board[d])
                return false;
            
            if(Math.abs(i - d) == Math.abs(board[i] - board[d]))
                return false;
        }
        
        return true;
    }
}

 

 

후기

백트래킹을 공부할 때 맨 처음 접하게 되는 대표적인 문제이다. 알듯말듯하다...