[프로그래머스/level 2] N-Queen - 12952

[level 2] N-Queen - 12952

문제 링크

성능 요약

메모리: 76.9 MB, 시간: 470.74 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 12월 02일 16:44:32

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

---

입출력 예

n	result
4	2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

 

 

 

제출 코드

n-queen 문제는 백트래킹을 활용해 풀 수 있다.

한 행마다, 각 열에 퀸을 두며 dfs 탐색을 진행한다.

백트래킹 되었다면, 두었던 퀸을 다시 회수한다.

 

백트래킹 조건은 다음과 같다

1. 같은 행에 퀸이 있다.

2. 같은 열에 퀸이 있다.

3. 대각선 위치에 퀸이 있다.

 

만약 모든 n개의 퀸을 둘 수 있다면, answer 를 1 증가시킨다.

class Solution {
    int n;
    boolean[][] board; // n x n의 체스판
    int answer = 0; // 퀸이 n개 배치되면 1씩 증가
    
    
    // 대각선이나 같은 행, 열에 퀸이 있는지 체크. 있으면 true, 없으면 false
    boolean checkCondition(int x, int y){
        for(int i=0; i<n; i++){
            if(board[x][i]) return true;
            if(board[i][y]) return true;
            if(x>=i && y>=i && board[x-i][y-i]) return true; 
            if(x>=i && y+i<n && board[x-i][y+i]) return true;
            if(x+i<n && y>=i && board[x+i][y-i]) return true; 
            if(x+i<n && y+i<n && board[x+i][y+i]) return true;
        }
        return false;
    }
    
    
    void backtracking(int row){
        // 마지막 행까지 퀸을 배치됐다면 answer를 1 증가시킴
        if( row == n){ 
            answer++;
            return;
        }
        
        for(int col=0; col<n; col++){
            if(checkCondition(row, col)) continue; // 백트래킹 조건에 걸리면 탐색 안함
            board[row][col] = true; // 해당 위치에 퀸 배치
            backtracking(row+1); // 재귀호출하여 다음 행 퀸 배치
            board[row][col] = false; // 해당 위치에 퀸 배치 취소
        }
    }
    
    
    
    public int solution(int n) {
        this.n = n;
        this.board = new boolean[n][n];
        backtracking(0);
        return this.answer;
    }
}