문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제
나의 풀이1
N = int(input())
board = [[False for _ in range(N)] for _ in range(N)]
total = 0
def attack_possible(i, j):
possiblity = True
# 같은 행 확인
if board[i].count(True) >= 1:
return False
# 같은 열 확인
for k in range(i):
if board[k][j]:
possiblity = False
break
# 대각선 오른쪽 위로 이동
a = i
b = j
while a >= 0 and b >= 0:
if board[a][b]:
possiblity = False
break
else:
a -= 1
b -= 1
# 대각선 왼쪽 위로 이동
c = i
d = j
while c >= 0 and d < N:
if board[c][d]:
possiblity = False
break
else:
c -= 1
d += 1
return possiblity
def backtracking(cnt, a, b):
if cnt == N:
global total
total += 1
return
for i in range(a, N):
for j in range(b, N):
if attack_possible(i, j):
board[i][j] = True
backtracking(cnt+1, i+1, 0)
board[i][j] = False
backtracking(0, 0, 0)
print(total)- 처음엔 2차원 배열로 접근했는데 시간 초과됐다.
나의 풀이2
N = int(input())
row = []
col = []
queens = []
total = 0
def attack_possible(i, j):
possiblity = True
# 대각선 확인
for a, b in queens:
if abs(i - a) == abs(j - b):
possiblity = False
break
return possiblity
def backtracking(cnt, a, b):
if cnt == N:
global total
total += 1
return
for i in range(a, N):
for j in range(b, N):
if i not in row and j not in col:
if attack_possible(i, j):
row.append(i)
col.append(j)
queens.append([i, j])
backtracking(cnt+1, i+1, 0)
row.pop()
col.pop()
queens.pop()
backtracking(0, 0, 0)
print(total)- 매번
attack_possible()실행하는 데 시간이 오래 걸리는 거 같아서 실행 시간을 줄이기 위해 열, 행, 대각선 별로 리스트를 만들어봤다. - 하지만 아직도 시간 초과
나의 풀이3
N = int(input())
row = [False]*N
col = [False]*N
queens = []
total = 0
def attack_possible(i, j):
possiblity = True
# 대각선 확인
for a, b in queens:
if abs(i - a) == abs(j - b):
possiblity = False
break
return possiblity
def backtracking(cnt, a, b):
if cnt == N:
global total
total += 1
return
for i in range(a, N):
for j in range(b, N):
if not row[i] and not col[j]:
if attack_possible(i, j):
row[i] = True
col[j] = True
queens.append([i, j])
backtracking(cnt+1, i+1, 0)
row[i] = False
col[j] = False
queens.pop()
backtracking(0, 0, 0)
print(total)- 리스트에
append()하는 방법 말고 리스트의boolean값을 수정하는 방법으로 풀어봤는데 또다시 시간 초과...
나의 풀이4
from collections import deque
N = int(input())
row = deque()
col = deque()
queens = deque()
total = 0
def attack_possible(i, j):
possiblity = True
# 대각선 확인
for a, b in queens:
if abs(i - a) == abs(j - b):
possiblity = False
break
return possiblity
def backtracking(cnt, a, b):
if cnt == N:
global total
total += 1
return
for i in range(a, N):
for j in range(b, N):
if i not in row and j not in col:
if attack_possible(i, j):
row.append(i)
col.append(j)
queens.append([i, j])
backtracking(cnt+1, i+1, 0)
row.pop()
col.pop()
queens.pop()
backtracking(0, 0, 0)
print(total)- 리스트에 요소를 추가, 삭제하는 데 시간이 오래 걸리는 거 같아서 리스트보다 연산 속도가 빠른
deque()로 교체해 봤다. - 아직도 시간 초과, 아무래도 완전히 다른 접근법을 찾아야 할 거 같다.
다른 사람의 풀이
N = int(input())
visited = [-1] * N
cnt = 0
def check(now_row):
for row in range(now_row):
if visited[now_row] == visited[row] or now_row - row == abs(visited[now_row] - visited[row]):
return False
return True
def dfs(row):
if row == N:
global cnt
cnt += 1
return
for col in range(N):
visited[row] = col
if check(row):
dfs(row + 1)
dfs(0)
print(cnt)- 1차원 리스트 하나에 행과 열을 모두 저장한다는 아이디어로 접근한 풀이 방법이다.
- 리스트의 인덱스는 행이고 요소의 값은 열이다. 예를 들어
visited[1] = 3이라면 체스를(1, 3)에 둔 것이다.- 기존의 백트래킹 풀이 방법과 다르게 수정한 요소를 되돌리지 않는 것이 특이하다고 생각했는데 어차피 현재 행을 기준으로 이전의 행들만 검사하면 되고, 앞의 열들(리스트 요소)은 현재에 맞게 수정됐기 때문에 가능한 것이다.
- 각 행에는 퀸을 하나만 둘 수 있기 때문에 만약
visited리스트의 마지막 인덱스에 도달한다면N개의 퀸을 놓는 데 성공한 것이 된다. check()에서는 해당 열과 대각선에 퀸을 놓을 수 있는지 여부를 검사한다. (인덱스 순서대로 진행되고 있기 때문에 이미 해당 행에 퀸을 놓을 수 있다는 것은 증명됐다)check()에서visited리스트에 동일한 열을 가진 값이 있거나 행과 열의 거리가 동일한 요소가 존재하는지(대각선 탐색) 확인해서boolean값을 출력한다.Python 3로는 시간 초과가 발생하고,Pypy3로 제출해야 문제를 통과할 수 있다.Pypy3는 자주 쓰는 코드를 캐싱하는 기능이 있기 때문에 복잡한 코드를 사용하는 경우에Python 3보다 실행속도가 빠르다고 한다.
