[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 9663번 _ N-Queen

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

9663번: N-Queen

[문제]

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

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

 

[입력]

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

[출력]

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

 

[아이디어]

1) 각 row와 col에 하나씩만 퀸을 놓을 수 있다.

2) row에 대해 하나씩 조건에 맞게 퀸을 놓아가면서, 백트래킹을 실시한다.

3) 원래 아래처럼 총 4개의 visit 배열을 관리해야한다. 하지만 row를 하나씩 차례로 채워간다고 가정하면, 3개의 배열만 관리해도 된다.

이때 각 대각선에 대한 visit 배열은 (2n-1)의 길이를 가진다. 또한 x-y의 경우 (-n+1)부터 (n-1)까지의 값을 가지게 되기 때문에, 0 index화 하기 위해서 n-1을 더해주었다.

# 시간초과
n=int(input())
visit2 = [False]*n
visit3 = [False]*(2*n-1)
visit4 = [False]*(2*n-1)
queens = [0]*n;cnt=0
def queen(k):
    global cnt
    if queens[-1]:
        cnt+=1
        return
    l = queens.index(0)
    for i in range(k,n):
        for j in range(n):
            if not visit2[j] and not visit3[i-j+n-1] and not visit4[i+j]:
                if l<k: return
                else:
                    visit2[j] = True; visit3[i-j+n-1] = True; visit4[i+j] = True
                    queens[k]=(i,j)
                    queen(i+1)
                    queens[k]=0
                    visit2[j] = False; visit3[i-j+n-1] = False; visit4[i+j] = False
queen(0)
print(cnt)

처음에 이런 느낌으로 접근했다가 시간초과가 났다. 아무래도 이중 for문이 생성되면서 불필요한 가지치기가 너무 많이 필요하기 때문인 것 같다.

 

# Pypy3 통과
n=int(input())
visit2 = [0]*n
visit3 = [0]*(2*n-1)
visit4 = [0]*(2*n-1)
queens = [];cnt=0
def queen(k):
    global cnt
    if k==n:
        cnt+=1
#         print(queens)
        return
    for j in range(n):
        a = k-j+n-1; b = k+j
        if not visit2[j] and not visit3[a] and not visit4[b]:
            visit2[j] = 1; visit3[a] = 1; visit4[b] = 1
#             queens.append((k,j))
            queen(k+1)
#             queens.pop()
            visit2[j] = 0; visit3[a] = 0; visit4[b] = 0
queen(0)
print(cnt)

수정한 코드도 Pypy3로 제출해야 통과되고, 파이썬으로는 통과되지 않았다. 가능한 모든 최적화를 한 것 같은데.. 좀 아쉽다. 어쨌든 핵심은 재귀적으로 같은 행위를 반복하며 해당 행위가 끝났을 때에 visit들을 원상복귀하며 for문을 이어가는 것이다.