[백준] 9663번 N-Queen 배치하기 - JAVA

 

 

 

 

 

✍️풀이방식 

 

 

1. 문제 분석

 

N-queen은 전형적인 백트래킹으로 풀 수 있는 문제이다.  크기 N × N 체스판 위에 퀸 N개를 서로 공격하지 않게 놓는 문제. 체스에서 퀸은 가로, 세로, 대각선으로 움직일 수 있으므로 같은 행, 열, 대각선에는 퀸이 동시에 존재할 수 없음. 즉 같은 행에는 퀸이 1개만 존재할 수 있음. 모든 행에 퀸을 1개씩 배치해야 N개의 퀸이서로 공격하지 않도록 놓을 수 있다. 

 

 

 

 

2. 풀이 과정  

 

• 퀸을 한 행씩 배치하면서, 현재까지 놓은 퀸이 조건을 만족하지 않으면 즉시 가지치기(백트래킹) -> 탐색을 종료하고 이전 단계로 돌아간다. 
• 마지막 행까지 퀸  배치 성공하면 경우의 수 +1, 백트래킹 전체를 종료하면 경우의 수를 출력한다. 
• 맨 위 행부터 시작해 각 행마다 퀸을 하나 씩 배치하며 가능한 모든 경우의 수를 찾는 방식 

 

 

백트래킹은 가지치기를 어떻게 할 것인지를 고민하는 것이 중요하다 

 

 

일차원 배열로 퀸 배치 정보를 충분히 저장할 수 있다. 일차원 배열의 인덱스를 행, 값을 열이라고 생각하자.  

 

 

	0
			0
0
		0

  

 

 

이렇게 퀸이 배치 되어있다면 다음과 같은 일차원 배열을 생성할 수 있다

 

 

인덱스	0	1	2	3
값	1	3	0	2

 

 

 

일차원 배열로 저장하면 공격 가능 여부를 쉽게 구현할 수 있다. 직선 공격 같은 경우엔 같은 열에 퀸이 존재하는 지 판단한다. 

추가하려는 값이 기존 배열에 존재하는 값이면 같은 열에 이미 퀸이 배치되어있다는 뜻이다  

 

 

이때 같은 행은 처음부터 각 행에 퀸을 하나씩만 배치하도록 구성했기 때문에 따로 검사하지 않아도 된다  

 

 

대각 공격 같은 경우엔 대각선상에 퀸이 존재하는 지 판단한다. 이때 인덱스의 차이와 값의 차이가 같은 데이터가 있다면 대각선상에 같은 퀸이 배치되어 있다는의미다.   

 

---

 

 

🖥️문제풀이

 

 

 

import java.io.*;
import java.util.*; 


public class Main
{   
    static int N; 
    static int[] A; 
    static int cnt = 0 ; 
        

	public static void main(String[] args) throws IOException {
        
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt(); // N개를 서로 공격할 수 없게 놓는 경우의 수 

        A = new int[N]; 
        
        backtraking(0);
        
        System.out.println(cnt);
        
        
	}
	
	public static void backtraking(int row){ // 0 행부터 시작 
	
	    if(row == N) { // 퀸 4개를 모두 배치한 경우 
	        cnt++; // 정답 출력 
	        return; 
	        
	    } 
	    
	    for(int i=0; i<N; i++){// 모든 경우의 수 탐색 
	    
	        A[row] = i ; // 퀸 배치 
	        if(check(row)){// 가지치기 유효성 검사 
	            backtraking(row+1); 
	        }
	        
	    }
	   
	}
	
	private static boolean check(int row){
	    for(int i=0; i<row ; i ++){
	        if(A[i]==A[row])return false; //직선 공격 방어 
	        if(Math.abs(row-i)==Math.abs(A[row]-A[i]))return false;// 대각선 공격 방어 (행,열 차이값 비교) 
	   
	    }
	    
	    return true; 
	    
	}

}

 

 

 

 

방법 1 

if (check(row)) { // 유효성 검사
    backtracking(row + 1); 
}

 

• row 자체 값은 바뀌지 않음
• 재귀 함수에 row+1을 인자로 넘겨줌
• 호출이 끝나고 돌아오면 row는 여전히 원래 값

 

방법 2 

if (check(row)) { // 유효성 검사
    row += 1; 
    backtracking(row); 
    row -= 1;  // 원상복구
}

 

• 여기서는 row 변수 자체를 직접 수정(+=1)
• 재귀 함수 호출 끝나고 나면 row -= 1 해서 다시 돌려놓음
• 결국, 호출 전후로 row 값은 그대로 유지됨

 

결과적으로 재귀 안에서는 row+1 상태로 동작하고, 재귀가 끝나면 원래 row 값으로 복구된다는 점에서 두 코드가 같다. 

• 단순 값(int, row 같은)일 때는 첫 번째 방법이 더 깔끔하다 
• 하지만 배열이나 리스트 같은 참조 타입을 다룰 땐, 두 번째 방식(값 수정 후 원상복구)이 흔히 쓰인다. 

 

 

결과