•
문제 링크
해당문제는 python3으로 제출하면 시간초과가 발생하니 pypy3로 제출하세요.
•
문제 설명
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구해야한다.
•
풀이 방법
접근방법이 생각이 안나서 다른사람의 풀이를 봤는데, 우선 퀸은 N개를 놓아야한다.
퀸은 같은 행, 열은 놓을 수 없기 때문에 각 퀸은 모두 다른 행/열 위치를 가진다.
그래서 모든 퀸을 각 행의 첫번째 열에 놓은 후, 마지막 열까지 한칸씩 이동하며 확인한다.
그렇게 마지막행까지 모두 적합한 위치라면 갯수를 증가시킨다.
이때 대각선을 확인하는 방법은 아래와 같다.
좌표(X, Y)와 (X, Y)좌표의 대각선 위치의 (A, B) 좌표는 X-A = Y-B 가 성립한다.
즉, 좌표(X, Y)와 행,열이 동일한 값만큼 떨어진 좌표가 대각선에 위치하는 좌표라는 말이다.
또한 동작시간을 조금이라도 줄이기 위해, 각 열에 퀸이 존재하는지 추가적으로 확인한다.
•
성공 코드
# 해당 위치에 퀸을 놓아도 되는지
def correct(row):
# 현재행 이전까지 모든 행의 퀸을 확인
# 현재 5행이라면, 1~4행의 이전 퀸들과 확인
for i in range(row):
# result[row] == result[i] : 같은 열이거나
# abs(row - i) == abs(result[row] - result[i]) : 대각선 위치일 때
if result[row] == result[i] or abs(row - i) == abs(result[row] - result[i]):
return False
# 이전의 모든 행의 퀸과 공격할 수 없을 때
return True
# 첫행부터 마지막행까지 반복(dfs)
def dfs(row):
# 마지막행까지 모두 적합한 위치일 때
if row == N:
global answer
answer += 1
return
# 각 행의 퀸을 첫 행 ~ 마지막 행까지 이동하면서 확인한다.
for i in range(N):
if visit[i]:
continue
# result[row] = column
# row행 column열에 퀸이 존재한다.
result[row] = i
# 다른 퀸과 겹치지 않는 적합한 위치일 때
if correct(row):
visit[i] = True
# 다음 행을 확인
dfs(row + 1)
visit[i] = False
N = int(input())
# N개의 퀸을 각 행의 첫 위치에 놓고 시작
result = [0] * N
# 이미 해당열에 퀸이 존재하는지 확인
visit = [False] * N
# 총 방법 갯수
answer = 0
dfs(0)
print(answer)
Python
복사