[BOJ] 9663. N-Queen

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

9663번: N-Queen

 

 

1. 해결방법

"""
1. 아이디어
- 체스판 위의 퀸은 같은 열과 행에 두개의 퀸이 존재할 수 없고, 왼쪽 및 오른쪽 대각선에 다른 퀸이 존재하는 경우가 되면 안된다.
- 2차원 배열을 이용할 경우, 퀸을 놓은 자리를 기준으로 열과 행, 대각선의 값을 1로 처리하고 방문기록도 체크한다. -> 2차원 배열을 사용하면 시간복잡도가 엄청나게 커짐.
- 열을 기준으로 한 리스트를 만들고 리스트 열 값에 퀸이 위치한 행 값을 넣는다.
- 퀸이 놓일 수 없는 위치면 재귀를 돈다.

2. 시간복잡도

3. 자료구조
- 백트래킹 : 재귀
"""

 

 

2. 정답코드

입력 예제(1)

8

출력 예제(1)

92

 

 

코드

import sys
input = sys.stdin.readline


# recur
def recur(num):
    global count

    # 재귀 종료 지점
    if num == n:
        count += 1
        return

    # 재귀
    for i in range(n):
        if chk[i] == False:
            graph[num] = i

            queen = True
            for j in range(num):
                if graph[num] == graph[j] or abs(num - j) == abs(graph[num] - graph[j]):
                    queen = False
                    break
            if queen:
                chk[i] = True
                recur(num + 1)
                chk[i] = False


# main
n = int(input())
count = 0
graph = [0] * n
chk = [False] * n
recur(0)
print(count)

 

내 수준에서는 확실히 어려웠다.
시간복잡도를 고려해서 열을 기준으로 리스트화 시키고 해당 리스트 원소 값에 퀸이 위치한 행의 값을 삽입한다.

아디이어를 알아도 if문을 이용한 코드로 옮겨 적기도 굉장히 힘들었다. 

그리고, Python 3로 제출을 하면 위 코드는 시간초과가 뜬다. PyPy 3로 제출하니깐 맞다고는 하는데 실행시간이 꽤 길다...
앞으로 문제를 더 많이 풀어봐야겠다.