코드의 구현 자체는 간단하다.
DFS를 돌면서, 조건에 맞도록 구현하면 된다.
발목을 잡았던 부분은 바로 시간초과였다. 15 * 15의 경우 상당한 연산 시간이 필요하기 때문으로 보인다.
이미 이전의 퀸들이 있는 곳은 제외하고 넘어가도록 해야 최대한 시간을 아껴야 통과할 수 있다.
결국 PyPy3에서는 성공했지만, Python3에서는 여전히 시간초과가 발생했다.
Python3에서도 성공하려면 뭔가 다른 방법이 필요할 것으로 보이지만, 시간이 아까우니 패스.
import sys
N = int(sys.stdin.readline())
row = [0] * N
cnt = 0
visit = [False] * N
# Queen이 서로 공격할 수 없는 지 확인
def check(q):
for i in range(q):
if abs(row[q] - row[i]) == q - i: # 대각선에 Queen이 있는지 확인
return False
return True
# DFS로 방법으로 탐색
def dfs(q):
global cnt
if q == N:
cnt += 1
return
for i in range(N):
if visit[i]: # 같은 열에 Queen이 있는가
continue
row[q] = i
if check(q):
visit[i] = True
dfs(q + 1)
visit[i] = False
dfs(0)
print(cnt)
'Study > Algorithm' 카테고리의 다른 글
[프로그래머스] 가장 큰 수 (Python) (0) | 2021.12.05 |
---|---|
[프로그래머스] 주식가격 (Python) (0) | 2021.12.02 |
[백준] 5430번: AC (Python) (1) | 2021.11.29 |
[백준] 10828번: 스택 (Python) (0) | 2021.11.25 |
[백준] 1920번: 수 찾기, 10815번: 숫자 카드 (Python) (0) | 2021.11.25 |