128. N-Queen

백준

1. Python

def check(n):
    for i in range(n):
        if row[n] == row[i] or abs(row[n]-row[i]) == n-i:
            return 0
    return 1
        
def dfs(n):
    global res
    if n == N:
        res += 1
    else:
        for i in range(N):
            row[n] = i
            if check(n):
                dfs(n+1)

N = int(input())
row = [0]*N
res = 0
dfs(0)
print(res)


출처: https://jinho-study.tistory.com/979

n = int(input())

def dfs(arr):
    global ans
    length = len(arr)

    if length==n:
        ans+=1
        return
        
    candidate = list(range(n)) # 후보가 될 수 있는 자리를 0부터 n-1까지 만들고 제외하는 방법을 사용
    for i in range(length):
        if arr[i] in candidate:  # 같은 가로줄에 있으면 후보에서 제외
            candidate.remove(arr[i])
        distance = length - i
        if arr[i] + distance in candidate:  # 같은 '/' 대각선에 있으면 후보에서 제외
            candidate.remove(arr[i] + distance)
        if arr[i] - distance in candidate:  # 같은 '\' 대각선에 있으면 후보에서 제외
            candidate.remove(arr[i] - distance)
    if candidate:
        for i in candidate:
            arr.append(i)
            dfs(arr)
            arr.pop()
    else:
        return

ans = 0
for i in range(n):
    dfs([i])
print(ans)

참고

2. C++

#include <cstdio>

int n, ans;
int chess[14][14];  // 초기화가 이미 0으로 되어있음  

// line : 0 ~ n - 1
void recur(int line) {
    // 종료조건
    if (line == n) {
        ans++;
        return;
    }
    // line어딘가에다가 queen을 놓아본다
    for (int i = 0 ; i < n ; i++) {
        if (chess[line][i] != -1) continue;
        chess[line][i] = line;
        // line에 놓았으니까 상/하/좌/우/대각선에는 queen을 놓지 못하게 처리한다 
        // 좌/우 
        for (int x = 0 ; x < n ; x++) {
            if (chess[line][x] == -1) {
                chess[line][x] = line;
            }
        }
        // 하
        for (int y = line ; y < n ; y++) {
            if (chess[y][i] == -1) {
                chess[y][i] = line;
            }
        }       
        // 대각선
        for (int y = line, x = i ; y < n && 0 <= x ; y++, x--) {
            if (chess[y][x] == -1) {
                chess[y][x] = line;
            }
        }
        for (int y = line, x = i ; y < n && x < n ; y++, x++) {
            if (chess[y][x] == -1) {
                chess[y][x] = line;
            }
        }

        // 다음 줄 queen을 놓아본다
        recur(line + 1);

        // 지금 queen이 처리한 흔적을 지운다.
        //자기가 그린 것만 지우기
        
        for (int x = 0 ; x < n ; x++) {
            if (chess[line][x] == line) {
                chess[line][x] = -1;
            }
        }
        // 하
        for (int y = line ; y < n ; y++) {
            if (chess[y][i] == line) {
                chess[y][i] = -1;
            }
        }       
        // 대각선
        for (int y = line, x = i ; y < n && 0 <= x ; y++, x--) {
            if (chess[y][x] == line) {
                chess[y][x] = -1;
            }
        }
        for (int y = line, x = i ; y < n && x < n ; y++, x++) {
            if (chess[y][x] == line) {
                chess[y][x] = -1;
            }
        }
        
        
        /*
        //그냥 다 지우기(초기화)
        
        //queen이 처리한 흔적을 지운다.
        for(int y = line; y < n; y++){
          for (int x =0; x < n; x++){
            if (chess[y][x] == line){
              chess[y][x] = -1;
            }
          }
        }
        
        */
        
        
    }
}

int main() {
    // array fill
    for (int i = 0 ; i < 14 ; i++) {
        for (int j = 0 ; j < 14 ; j++) {
            chess[i][j] = -1;
        }
    }
    scanf("%d", &n);
    // todo
    recur(0);
    printf("%d", ans);
}

3. Java