ALGORITHM

[JAVA] 백준 9663번- N-Queen

연듀 2023. 1. 4. 12:09

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

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

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

public class Main {
    static int n;
    static int[] col;
    static int cnt = 0;

    static boolean check(int y) {
        for (int i = 0; i < y; i++) { // y행 이전의 행들 비교
            if (col[y] == col[i] || Math.abs(y - i)==Math.abs(col[y] - col[i])) // 같은 열에 퀸이 있거나 대각선에 있으면
                return false;
        }
        return true;
    }

    static void dfs(int y) {
        if (y == n) { // n번째 행까지 퀸 n개를 다 놓았다면
            cnt++;
            return;
        }
        for (int i = 0; i < n; i++) {
            col[y] = i; // y번째 행의 i번째 열에 퀸을 배치
            if (check(y)) dfs(y + 1); // 놓을 수 있다면 다음 행에 퀸 배치
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        col = new int[n]; // col[index] = n --> index번째 행의 n번째 열에 퀸이 있음

        dfs(0);
        System.out.println(cnt);
    }
}

 

'ALGORITHM' 카테고리의 다른 글

[JAVA] 백준 2580번- 스도쿠  (0) 2023.01.06
[JAVA] 백준 16198번- 에너지 모으기  (0) 2023.01.04
[JAVA] 백준 11663번- 선분 위의 점  (0) 2022.12.30
[JAVA] 백준 2512 - 예산  (0) 2022.12.30
[JAVA] 백준 2343 - 기타 레슨  (0) 2022.12.29