[JAVA52] 9663. N-Queen

9663. N-Queen (G4)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	125157	60365	38997	46.691  %

 

문제

 

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

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

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

.

---

summary

퀸을 놓을 수 있는 경우의 수

• 퀸은 상하좌우, 대각선에 위치가 공격

 

strategy

완전탐색 (백트래킹) 활용

• 퀸의 공격 대상인 세로, 가로, 대각선을 중복 사용 방지
• 가로 중복 체크 (witdh)
• 오른쪽아래 대각선 (sumCross)
• 왼쪽아래 대각선 (subCross)

 

note

• 1 ≤ N < 15

 

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

public class Main {

    static int N;
    static boolean[] width, sumCross, subCross;
    static long answer = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        width = new boolean[N];
        sumCross = new boolean[2*N];
        subCross = new boolean[2*N];

        NQueen(0); // 0 행 시작

        System.out.println(answer);

        br.close();
    }

    public static void NQueen(int row) {

        if(row == N) { // 종료조건
            answer++;
            return; 
        }

        for(int col = 0; col < N; col++) {
            if(width[col] || sumCross[row + col] || subCross[(N-1) + row - col]) continue;

            width[col] = true;
            sumCross[row + col] = true;
            subCross[(N-1) + row - col] = true;

            NQueen(row + 1);
            
            width[col] = false;
            sumCross[row + col] = false;
            subCross[(N-1) + row - col] = false;
        }
    }
}

문제	결과	메모리	시간	언어코드	길이
9663	맞았습니다!!	14828 KB	2420 ms	Java 11 / 수정	1130 B

 

memo

• N이 15여서 긴가민가했는데 15는 포함안된거였음 (13! 이 10억인데, 가지치기해서 14억이 간신히 되는듯)
• 또 다른 방법, 열의 차와 행의 차가 같으면 같은 대각선임 (각 행열에 위치를 저장하는 방식 시 가능)

[백준] 9663번 : N-Queen - JAVA [자바]