[백준 9663번/java] N-Queen

문제

https://www.acmicpc.net/problem/9663

 

풀이

*백트래킹 문제에 아직 익숙하지 않아서 풀이 방법을 본 후에 코드를 짰다. (참고 블로그)

https://chanhuiseok.github.io/posts/algo-23/

https://chanhuiseok.github.io/posts/baek-1/

 

NxN 체스판에 N개의 퀸을 서로 공격할 수 없도록 놓는 문제이다.

퀸이 놓인 자리의 가로, 세로, 대각선에 다른 퀸이 놓일 수 없게 해야 한다.

 

가로, 세로, 대각선인지 검사한 후 제외하는 아이디어까지는 생각해냈는데,

N개의 퀸을 놓는 모든 경우의 수를 구하기 위해서는 어떤 구조로 코드를 작성해야 좋을 지 떠올리는 게 힘들었다.

 

그리고 참고한 풀이에서 이차원 배열을 사용하지 않고 일차원 배열의 인덱스를 행으로, 값을 열로 간주하고 위치를 찾아야 해서 더 오래 붙잡고 있었다.

//수도코드도 없이 처음 짜본 코드 

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

public class boj_9663 {
    static int N;
    static int[] arr;
    public static void main(String[] args) throws IOException{
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        arr = new int[N]; //각 행이 몇 열인지 저장할 배열

        for(int i=0; i<N; i++){
            //0행의 0~N-1열까지 첫 퀸으로 설정
            arr[0] = i;

            //1행부터 끝까지 유효성 검사하면서 진행


        }
    }

    //유효성을 검사하는 함수
    static int valid(int x){
        //x행의 각 열이 유효한지 아닌지 검사
        //가장 먼저 유효한 것으로 판단된 열을 반환.
        int ans = -1;
        for(int i=0; i<N; i++){
            for(int j=0; j<x; j++){
                //같은 열이 아님
                if(arr[j] == i)
                    continue;
                //대각선이 아님
                if(Math.abs(arr[j]-i) == Math.abs(j-x))
                    continue;
            }
            ans = i;
            break;
        }
        return ans;
    }
}

 

다음은 풀이를 완전히 이해하고 다시 짜본 코드이다. 아래 과정에 따라 코드를 완성했다.

 

1. N 입력받기

2. int[N] arr 생성

3. 0행 0열부터 0행 N-1열까지 각각 첫 퀸을 놓으면서 가지치기해나가며 경우의 수를 구하기 + 백트래킹

4. 3번 과정에서 N행까지 퀸이 놓였다면 count++

5. count를 출력

//3번 과정

//x행 y열에 퀸을 놓는 함수
void nqueen(x) //x행
	for(y:0->N-1) //y열
    	arr[x] = y //x행 y열에 퀸을 놓기
    	if(promising(x)) //유효하면
        	nqueen(x+1) //다음 행 진행
            
            
//퀸을 놓을 수 있는 자리인지 (자리가 유효한지)확인하는 함수
boolean promising(x)
	for(i:0->x-1) //그 전의 모든 행에 놓인 퀸과 비교해서, 같은 열이 아님 or 대각선이 아님
    	if(arr[x] == arr[i] || x-i == Math.abs(arr[x] - arr[i]))
        	return false;
    return true;

arr[x] = y (x행 y열에 퀸을 놓는 코드)를 유효한지 확인한 후에 배치하려고 했는데, 잘못된 방법이었다.

유효한지 확인하려면 먼저 그 자리에 퀸을 놓아야 하기 때문이다. 

 

어차피 promising()에서 유효한지 확인하기 위해 arr[x] = y과정이 필요하다.

그래서 유효한지 확인하기 전에 nqueen()에서 먼저 arr[x] = y을 실행한 후 promising()을 호출했다.

코드

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

public class boj_9663 {
    static int N;
    static int[] arr;
    static int count;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        arr = new int[N];
        nqueen(0);
        System.out.print(count);

    }
    static boolean promising(int x){
        //x행 y열에 놓인 퀸이 유효한지 확인
        for(int i=0; i<x; i++){
            if(arr[x] == arr[i] || x-i == Math.abs(arr[x] - arr[i]))
                return false;
        }
        return true;
    }
    static void nqueen(int x){
        if(x == N){ //마지막 행까지 퀸을 놓은 경우
            count++;
            return;
        }
        for(int y=0; y<N; y++){
            arr[x] = y; //x행 y열에 퀸을 놓음
            if(promising(x)) //그 자리가 유효하다면
                nqueen(x+1); //다음 행 진행
        }
    }
}