백준 9663 N-queen

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

9663번: N-Queen

📌 해결순서 

퀸은 현재 위치에서 상하좌우, 4방향 대각선을 칸의 제한없이 이동할 수 있다.

체스판위의 모든 퀸이 서로를 공격할 수 없게 만들기 위해서는

1. 모든 퀸이 서로 같은 열, 행에 위치하면 안됨

2. 하나의 퀸에 대한 모든 4가지 대각선 방향에 퀸이 위치하면 안됨

 

만약, 모든퀸이 서로를 공격할 수 없게 만든다면 각 행에 하나의 퀸만 존재하기 때문에, 

row = [0] * n 인 1차원 배열을 생성해서 배열의 인덱스가 행, 배열의 값이 열 이렇게 생각해볼수 있다.

첫번째 행의 모든 열에 대해 백트래킹을 사용한 dfs 완탐을 하면 답을 구할수 있다.

간단한 4 X 4 체스판에 적용해보면 다음과 같다

 

우선 , row[0] = 0 으로 (0, 0)에 첫번째 퀸을 두고 탐색을 시작한다

 

row[1] , 다음 행에서는 처음행과 같은열에 있는 위치, 처음행과 대각선에 있는 위치에 대해서는 퀸을 놓을수 없으므로 방문하지 않고 조건을 만족하는 위치를 찾는다

이 경우에는 row[1] = 2 즉, (1, 2) 위치에 2번째 퀸을 위치 시킨다

 

row[2] 의 모든 열에 대해서 위치 시킬수 있는 퀸의 좌표가 없으므로 탐색을 마무리 하고 백트래킹으로 row[1] = 3 에 대해서 탐색한다.

 

row[2] = 0 에 놓을수 있으므로 row[3] 에 대해서 탐색을 하고, row[3] = 2 에 퀸을 위치시킬수 있다. 

따라서 cnt += 1을 해준다

이 경우 row 배열은 다음과 같다.

 

이제 남은 row[3] = 3 에 대해서 판단을 한 뒤,

row[2] = 1 ~ 3 에 대해서도 동일한 탐색을 진행하고, 다시 row[0] = 2 부터 모든 탐색을 진행한다.

📌 코드

pypy3 으로 제출 해야함

import sys
input = sys.stdin.readline


def keep_search(x):
    for i in range(x):
        # 대각선 비교
        # 행 - 행 == 열 - 열 이면 대각선에 위치한다
        if row[x] == row[i] or x - i == abs(row[x] - row[i]):
            return 0
    return 1


def dfs(x):
    global cnt
    if x == n:
        cnt += 1
    else:
        for i in range(n):
            # row[0] = 0
            row[x] = i
            if keep_search(x):
                dfs(x + 1)


n = int(input())
row = [0] * n
cnt = 0
dfs(0)
print(cnt)

아마 그냥 python3 을 이용해서 맞았습니다를 띄우려면 열 , 행 , 대각에 대한 visited 배열을 만들어서 백트래킹을 진행해야 할듯 싶다..