[백준/Python] 9663번 - N-Queen

 

문제

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

 

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오

 

 

 

입력

 

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

 

출력

 

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

 

풀이

 

시간 초과로 인해 pypy로 풀었다.

체스판의 크기 N이 주어지면 길이가 N인 리스트를 만든다. 리스트의 인덱스 i(0~N-1)를 체스판의 행이라 생각하고 i번째 행에 몇번째 칸에 퀸이 들어갈 수 있는지를 비교해 리스트에 저장해가며 탐색했다.

 

퀸이 놓인 칸으로부터 대각선과 직선의 범위에는 다른 퀸이 놓일 수 없으므로 i번째 줄의 퀸은 이전 퀸들의 열이 겹치지 않아야 한다.

 

그리고 대각선에 있기 위한 조건은 퀸이 놓이는 행과 열에서 다른 퀸의 행과 열을 뺐을 때 절대값이 같으면 대각선에 있기 때문에 비교해서 제외해 줬다.

 

 

Code

 

 

def backt(k):
    global num
    if k==N:
        num+=1
        return
    for i in range(N): #i==x j==y i는 열의 위치를 나타낸다
        if not visited[i]: # 만약 다른 퀸이 열에 없다면
            for j in range(k): # 다른 퀸들이 대각선에 있는지 비교 
                if k-j==abs(i-visit[j]):
                    break
            else: # 대각선과 열에 없다면 i번째 열에 방문표시를 하고 다음 행으로 넘어간다.
                visit[k]=i 
                visited[i]=True
                backt(k+1)
                visited[i]=False

N=int(input())
visit=[-1]*N # 저장할 리스트
visited=[False]*N # 방문표시
num=0
backt(0)
print(num)

 

---

 

시간을 더 줄이려면 대칭을 이용해야 할 것 같다.

 

9663번: N-Queen