[백준]9662: N-Queen - JAVA

[백준]9662:  N-Queen

 

 

www.acmicpc.net/problem/9663

9663번: N-Queen

풀이

프로그래머스에 있는 N-QUEEN문제와 동일한 문제이다. DP문제의 대표가 하노이의 탑이 있다면 순열 문제의 대표라고 할 수 있는 문제이다.

 

이전에 풀었던 적이 있지만 오래되어 다시 한번 풀어보았다. 다시 풀자니 역시 조금 헤메이는 부분이 있었다. 게다가 백준의 문제 설명이 부족한 것도 있다. 프로그래머스에는 문제 설명이 자세히 잘 되어 있으니 N-QUEEN문제는 프로그래머스에 푸는 것을 추천한다.

 

아래는 이전에 프로그래머스에서 풀었던 풀이 방식이다. 사실 똑같은 문제이므로 아래 페이지를 참고하면 될 것 같다.

 

https://moonsbeen.tistory.com/34?category=1184370

[프로그래머스]N-Queen - JAVA

코드

import java.util.*;
 
public class Main {
    
    static int n;
    static int[] col;
    static boolean[] visited;
    static int count = 0;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        col = new int[n];
        
        visited = new boolean[n];
        backtracking(0);
        System.out.println(count);
    }
    
    public static void backtracking(int idx) {
        if(idx == n) {
            count++;
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(visited[i] == false) {
                visited[i] = true;
                col[idx] = i;
                if(check(idx)) backtracking(idx + 1);
                visited[i] = false;
            }
        }
    }
    
    public static boolean check(int x) {
        for(int i = 0; i < x; i++) {
            if(col[i] == col[x]) return false;
            else if(Math.abs(x - i) == Math.abs(col[x] - col[i])) return false;
        }
        return true;
    }
}