[알고리즘풀이]백준 9663: N-Queen JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이전에 알고리즘 스터디에서 JAVA를 이용해 백준 9663번 N-Queen을 풀었습니다. 이를 정리해보고자 합니다.

9663번: N-Queen

 

본문

1) 문제

2) 과정

아주 대중적인 문제이지만 푸느라 많은 시간이 걸렸습니다.

최소 3시간은 썼던 문제였던 것 같네요!

 

2-1) main

    private static int n, ans=0;
    private static int[] chess;

    public static void main(String[] args) throws IOException {
        input();
        func(0);
        output();
    }

main은 다음과 같습니다. input과 func, output으로 구성하였습니다. 각각은 아래 나올 내용의 Input, Logic, Output입니다.

그리고 사용할 변수를 전역변수로 선언해줍니다.

n, ans, chess[]는 각각 퀸의 수, 정답인 서로 공격할 수 없게 놓는 경우의 수, 한 줄에 퀸이 있는지를 담는 배열입니다.

 

2-2) Input

    private static void input() throws IOException {
    	// Input
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine());

		// Initialize
        chess = new int[n];
    }

 

읽어오는 것 관련된 정보는 아래 링크를 확인해주세요 :)

[개념정리] System.in / InputStreamReader / BufferedReader 정리

첫번째 줄을 읽어 n에 값을 넣어줍니다. 이후 n의 크기로 int배열 chess를 new해줍니다.

 

2-3) Logic

    private static void func(int y) {
        // 모든 열을 다돌았을 경우
        if(y==n){
            ans++;
            return;
        }
        for(int x=0;x<n;x++){
            // 해당 x에 값을넣고
            chess[y]=x;
            // 그경우 이전것과 비교하여(가로세로, 대각선) 가능한가 체크하여 재귀호출
            if(promising(y)) func(y+1);
        }
    }

    private static boolean promising(int y){
        //지금까지 쌓아온걸로 해당 열에 들어갈 수 없게하는 조건들 확인
       for(int row=0;row<y;row++){
           // 가로세로 비교
           if (chess[row] == chess[y]) return false;
           // 대각선 비교
           else if (Math.abs(y-row)==Math.abs(chess[y]-chess[row])) return false;
       }
       return true;
    }

func(0)로 func를 처음 불러줍니다. func는 경우를 찾아나가는 함수이고, promising은 파라미터로 받은 y에 퀸이 들어갈 수 있는지 확인하는 함수입니다.

 

func는 종료 조건 부분과 열을 탐색해나가는 부분으로 구성됩니다.

종료조건 부분은 모든 열을 다 돌았을 경우(y==n), 가능한 경우를 담는 변수 ans에 1을 더해줍니다. 

열을 탐색해나가는 부분은 먼저 한 열에 퀸이 있다고 넣은 뒤, 다음 열에 퀸이 들어가는데 문제가 없다면 func를 통해 다음 열을 탐색할 수 있도록 합니다.

 

promising은 지금까지 쌓인(0~y) 체스판이 문제가 없는지 체크합니다.

파라미터로 받은 y까지 각 row를 살피며 가로, 세로, 대각선을 비교합니다. 이 때 퀸을 놓을 수 없는 조건일 경우 false를 리턴합니다. 모든 row에 문제 없이 for문을 빠져나오면  true를 리턴하면서 종료합니다.

2-3) Output

    private static void output() {
        System.out.println(ans);
    }

계산한 경우의 수 ans를 출력합니다.

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ9663 {
    private static int n, ans=0;
    private static int[] chess;

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine());

        chess = new int[n];
    }

    private static void func(int y) {
        // 모든 열을 다돌았을 경우
        if(y==n){
            ans++;
            return;
        }
        for(int x=0;x<n;x++){
            // 해당 x에 값을넣고
            chess[y]=x;
            // 그경우 이전것과 비교하여(가로세로, 대각선) 가능한가?
            if(promising(y)) func(y+1);
        }
    }

    private static boolean promising(int y){
        //지금까지 쌓아온걸로 해당 열에 들어갈 수 없게하는 조건들 확인
       for(int row=0;row<y;row++){
           // 가로세로 비교
           if (chess[row] == chess[y]) return false;
           // 대각선 비교
           else if (Math.abs(y-row)==Math.abs(chess[y]-chess[row])) return false;
       }
       // 모든 조건 만족시 true
       return true;
    }

    private static void output() {
        System.out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        input();
        func(0);
        output();
    }

}

 

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/bruteforce/BOJ9663.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비