[9663_백준] N-Queen 문제풀이 (java)

안녕하세요,

오늘은 백트래킹의 가장 대표 유형 문제인 N-Queen 문제를 풀이해보겠습니다.

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

9663번: N-Queen

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

핵심 로직

- 백트래킹 (재귀 활용) 

 

풀이 방식

1. 가장 윗 열부터 시작하여 퀸을 놓을 수 있는 지, 없는 지 여부 확인 > 조사 범위를 윗열로 한정 가능

2. 중간에 불가능한 row가 발견되면? 뒤로 돌아가서 마지막으로 한 거 없애기 > 백트래킹 알고리즘 활용

3. row가 N까지 도달했다 ( 기저조건을 만족할 수 있다) == 퀸을 둘 수 잇는 경우다 > cnt ++ 

 

풀이코드

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

public class Main { 
    static int cnt, N;
    static int[] dr = {-1,-1,-1}, dc = {-1,0,1}; //조사할 윗 방향 설정 왼쪽위,위,오른쪽위
    static int[][] chessMap;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            N = Integer.parseInt(br.readLine());
            cnt = 0;
            chessMap = new int[N][N];
            Put_Queen(0);
            System.out.println(cnt);
    }

    //각 열마다 체크
    public static void Put_Queen(int row) {
        //기저 조건
        if (row >= N) { //여기까지 왔다는 얘기는?! 놓을 수 있는 경우라는 얘기!
            cnt++;
            return;
        }
        //재귀 조건
        for (int j = 0; j < N; j++) {
            //현재 row의 j번째 열에 퀸을 위치시킬 수 있는 지 파악
            if (!QueenCanPosition(row, j)) continue; //거기 놓을 수 없어? 그럼 다음 열보자
            chessMap[row][j] = 1; //여기 한 번 둬볼까?
            Put_Queen(row + 1); // 뒀다고 치고, 다음 거 확인 해보자
            chessMap[row][j] = 0; //둔 거 다시 치워야지
        }
    }
    public static boolean QueenCanPosition(int i,int j) { //Queen을 놓아도 되는 지 여부 판단
        for(int dir = 0; dir<3; dir++) { //세 방향 탐색하자
            int r = i;
            int c = j;
            while(r >= 0 && c >= 0 && c < N){  //경계조건에 있을 땐
                r += dr[dir];
                c += dc[dir];
                if(r >= 0 && c >= 0 && c < N && chessMap[r][c] == 1) return false; //거긴 못 지나간다..
            }
        }
        return true; // 들어가도 된다는 얘기
    }
}

 

 

읽어주셔서 감사합니다