[ 백준 / Python ] #9663 N-Queen

문제

 

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

9663번: N-Queen

---

Algorithm

n*n개의 타일에 퀸 n개를 서로 공격할 수 없게 되는 경우의 수를 출력하는 문제이다. 체스에서 퀸은 상하좌우, 대각선을 전부 이동할 수 있으므로 같은 열에는 둘 수 없다. n개의 열에 n개의 퀸을 두므로, 한 열에는 퀸이 1개만 존재해야한다. 순열을 재귀함수로 구현할때, 배열을 만들어서 선택이 가능한 경우에만 재귀함수를 돌리는 거에서 착안하여 재귀를 돌릴때마다 그 자리에 퀸을 두어도 되는지 안되는지 확인하기 위해 visited라는 배열을 만들고, 그 자리에 두었으면 상하좌우, 대각선에 두면 안되도록 배열의 값을 조정해준다.

n을 입력받고, n*n 크기의 visited배열을 만들어준다. 이때 True,False로 만들지 말고, 초기값을 모두 0으로 만들어준다. 이유는 이따가 봐보자

재귀함수 recur을 선언해주고, cur을 현재 열로 생각하고 변수를 만들어둔다. cur이 n이면 n개의 퀸이 서로 공격할 수 없는 경우이므로 return하고 cnt+=1을 해준다. 이제 cur열에 퀸을 둘건데, 아까 만든 visited배열의 cur열이 0보다 크면 continue로 제외를 시켜준다. cur열 i행에 퀸을 두었다면 cur+1부터 n까지의 i행을 전부 +=1로 해준다. 왜 +=1을 하냐면 True False로 설정해주면 이따가 재귀함수가 cur+1부터 n까지 다 돌고 나와서 cur열 i+1행에 두었을때를 찾아야하는데, 이때 초기화 하는 과정에서 이러한 오류가 나올 수 있다.

visited배열을 True False로 설정했을 때 제일 왼쪽이 cur-1열 까지 퀸을 둔 모습이고, 가운데가 cur열에 퀸을 두고 난 뒤의 visited배열이다. 그 다음에 cur+1부터 n까지 돌고 난 뒤에 초기화를 한 모습이가장 오른쪽에 있는 그림이다. 왼쪽과 오른쪽이 같아야하는데 다른 모습이다. 그래서 int로 초기값을 잡아주고 +1, -1을 해주었다. 

이제 퀸을 기준으로 왼쪽, 오른쪽 대각선 지점의 배열의 값을 +=1을 해주고 재귀함수를 호출해서 recur(cur+1)로 다음열로 넘어간다. 재귀함수가 다 돌고 나오면 초기화를 위해 +1해주었던 지점을 전부 -1해준다.

현재 행을 기준으로 아래쪽 행들의 값만 조정해 주면 가능한 경우만 보게 되도록 설정하고, cur이 n에 도달하면 퀸들이 서로 공격할 수 없으므로 cnt값을 더해주면 된다!

그리고 recur(0)을 해주고, cnt값을 출력해주면 값이 나온다!

---

 

 

Code

input = __import__('sys').stdin.readline

n = int(input())
visited = [[0 for _ in range(n)]for _ in range(n)]
cnt = 0
def recur(cur):
    global cnt
    if cur == n:
        cnt+=1
        return

    for i in range(n):
        if visited[cur][i] > 0: #현재 cur열에서 행을 보는데 visited값이 0보다 크면 여기에 두면 안되므로 pass
            continue

 #(cur,i)를 선택했으므로 이 지점을 기준으로 아래, 우하향 대각선, 좌하향대각선을 전부 두면 안되도록 설정
        for t in range(n-cur):
            visited[cur+t][i] +=1 # cur ~ n까지 두면 안되도록 설정
        x = 1
        while True: # (cur,i)를 기준으로 좌하향 대각선에 두면 안되도록 설정
            if cur+x > n-1 or i-x <0: 
                break
            visited[cur+x][i-x] += 1
            x+=1

        x = 1
        while True: # (cur,i)를 기준으로 우하향 대각선에 두면 안되도록 설정
            if cur + x > n - 1 or i + x > n-1:
                break
            visited[cur + x][i + x] += 1
            x += 1

        recur(cur+1) # 재귀 호출후 다음 열로 넘어감
        
        # 재귀가 다 돌고 나오면 이전상태로 리셋한다.
        
        for t in range(n - cur):
            visited[cur + t][i] -= 1
        x = 1
        while True:
            if cur + x > n - 1 or i - x < 0:
                break
            visited[cur + x][i - x] -= 1
            x += 1

        x = 1
        while True:
            if cur + x > n - 1 or i + x > n - 1:
                break
            visited[cur + x][i + x] -= 1
            x += 1

recur(0)

print(cnt)