[백준] 9663번: N-Queen

문제 내용

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

9663번: N-Queen

 

풀이 시간

24분

풀이 과정

백트래킹을 이용하여 풀이

promising 조건 찾는데에 시간을 대부분 소비

 

정답 코드

 

1. 파이썬

#pypy3로 해서 통과함
import sys
sys_input=sys.stdin.readline

n=int(sys_input())
cur=[]
ans=0

def success(row,col):
    for x,y in cur:
        if col==y or row+col==x+y or row-col==x-y:
            return False

    return True

def back_tracking(level):
    if len(cur)==n:
        global ans
        ans+=1

        return

    for i in range(1,n+1):
        if success(level,i):
            cur.append((level,i))
            back_tracking(level+1)
            cur.pop()

back_tracking(1)
print(ans)

 

 

2. 자바

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

public class Main {
    public static int n, ans = 0;
    public static List<Integer> cur = new ArrayList<>();

    public static boolean promising(int y) {
        for (int nx = 0; nx < cur.size(); nx++) {
            if (cur.get(nx) == y || cur.size() - nx == Math.abs(cur.get(nx) - y)) {
                return false;
            }
        }

        return true;
    }

    public static void back_tracking() {
        if (cur.size() == n) {
            ans += 1;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (promising(i)) {
                cur.add(i);
                back_tracking();
                cur.remove(cur.size() - 1);
            }
        }
    }

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

        System.out.println(ans);
    }
}