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

iamjinseo·2023년 10월 13일

백트래킹 프로그래머스

문제풀이-Java

목록 보기

44/53

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

문제 설명

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

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

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

제한사항

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

입출력 예

n	result
4	2

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

풀이

class Solution {
    static int[] queenCoor; //퀸이 어떤 행의 어떤 열에 놓였는지 나타내는 배열
    static int answer=0;
    static int N;
    public int solution(int n) {
        N = n;
        queenCoor = new int[n];
        
        setQueen(0);
        
        return answer;
    }
    
    // row행에 어떤 열에 퀸 놓을지 결정
    public static void setQueen(int row){
        
        // 백트래킹: 현재까지의 상태가 가능한건지 검사
        if(row>0 && !isAvailable(row-1)){
            // System.out.println(row-1+"행에 놓은거 망한듯");
            return;
        }
        
        // 기저조건: row가 n을 넘길때까지 setQueen을 했다는 건 조건에 만족
        if(row>=N){
            answer+=1;
            
            // for(int i : queenCoor){
            //     System.out.print(i+" ");
            // }
            // System.out.println();
            return;
        }
        
        
        // 이 행에서 열마다 퀸 놓기
        for(int c=0; c<N; c++){
            queenCoor[row] = c;
            // System.out.println(row+"행 "+c+" 열에 퀸을 놓음");
            setQueen(row+1);
        }
    }
    
    // row까지의 행에 놓인 퀸들 살피며 N Queen 조건 만족하는지 검사
    public static boolean isAvailable(int row){
        for(int r=0; r<row; r++){
            if(queenCoor[r] == queenCoor[row] || 
               Math.abs(queenCoor[r]-queenCoor[row]) == row-r)
                return false;
        }
        return true;
    }
}

백트래킹 연습문제중 가장 대표적인 N-Queen 문제이다.

전체적인 시나리오는 아래와 같다. (~~주석만 읽어도 좋다~~)

0행부터 퀸을 놓는다

setQueen(0);

1-1. 일단 0열부터 n-1열에 한 번씩 퀸을 놓는다
1-2. 퀸을 놓음과 동시에 바로 다음 행에 퀸을 넣어보자

    public static void setQueen(int row){
		...(생략)
        // 이 행에서 열마다 퀸 놓기
        for(int c=0; c<N; c++){
            queenCoor[row] = c;
            setQueen(row+1);
        }
    }

1행에 퀸을 놓는다
2-1. 지금까지 퀸을 놓은 상태가 적절한건지 검사해본다. 적절하지 않으면 재귀를 중단하고 이전 행으로 돌아간다.
// 백트래킹: 현재까지의 상태가 가능한건지 검사
if(row>0 && !isAvailable(row-1)){
    return;
}
2-2. 1행의 0열부터 n-1열에 한 번씩 퀸을 놓는다
2-3. 퀸을 놓음과 동시에 바로 다음 행에 퀸을 넣어보자.
for(int c=0; c<N; c++){
    queenCoor[row] = c;
    setQueen(row+1);
}

이 로직이 n-1행까지 굴러간다.
마지막에는 기저조건이 필요하다.

n행이 되었다. 이제 0부터 n-1까지 각 행에 하나씩 퀸이 놓아졌다. 백트래킹을 수행했음에도 여기까지 왔다는 건 N-Queen을 만족한다는 뜻이다. 경우의 수를 추가한다.
// 기저조건: row가 n을 넘길때까지 setQueen을 했다는 건 조건에 만족
if(row>=N){
    answer+=1;
    return;
}