2021년 07월 26일
사실 오늘 갑자기 예전에 썼던 글을 다시 끌어온 것은 이 글 때문이다...
오늘 우연히(?) 백트래킹 문제를 몇 개 풀었는데, 문제 하나가 분명 백트래킹으로 해야할 것 같은데 방법이 도저히 떠오르지 않아 이게 어떻게 힘이 되어주지 않을까 싶어서 다시 보려고 찾다보니 이렇게 되었다. 아무튼!
백트래킹 공부하기(4)
N-Queen 문제 마무리
기존에 2차원으로 해결하려고 했던 방법이 당연히 시간 초과가 나고,
오랜 고민 끝에 2차원이 아닌 1차원으로 해결할 방법을 생각해냈다.
만약 (x, y) 에 퀸을 놓았다면 (x, n) 에 해당하는 모든 칸에는 퀸을 둘 수 없고,
(n, y)에 해당하는 모든 칸에도 둘 수 없다. 확인할 필요가 없다는 얘기다.
이것을 단순 n칸짜리 리스트로 체크했다.
예를 들어, (0, 0)에 퀸을 놓았다면 0번 인덱스에 체크를 한다. y가 0인 좌표에는 퀸을 둘 수 없다는 의미.
또 (x, y)의 대각선에 있는 점에는 퀸을 둘 수 없다.
대각선은 퀸을 놓은 (x, y)를 기준으로 왼쪽 위에서 오른쪽 아래로 내려가는 대각선은 x-y의 값이 같고,
왼쪽 아래에서 오른쪽 위로 올라가는 대각선은 x+y의 값이 같다. 이를 두 개의 리스트로 나누어 각각 체크했다.
총 3개의 리스트로 체스판의 모든 위치 체크가 가능해졌다.
여기서부터는 앞서 사용했던 백트래킹 개념을 활용해 적용해주면 된다.
백트래킹 문제여도 상태를 어떻게 기록할 것인지를 잘 생각해내야 한다는 것을 알게 된 문제였다.
그리고 python3으로 제출했다가 시간 초과가 나서 더 줄여야하나 한참 코드를 들여다보며 고민했는데,
아무리 봐도 줄일 수 없었다. pypy3으로 제출하니 통과가 되었다. 다음부터는 두 가지로 다 제출해보고 고민해야겠다;;;
from sys import stdin
n = int(stdin.readline())
checkj = [0 for i in range(n)] # 세로
checkimj = [0 for i in range(2*n-1)] # i-j 왼쪽위에서 오른쪽아래로 내려가는 대각선
checkipj = [0 for i in range(2*n-1)] # i+j 왼쪽아래에서 오른쪽위로 올라가는 대각선
count=0
def Nqueen(i):
global count
if i==n:
count+=1
return
else:
for j in range(n):
if checkj[j]==0 and checkipj[i+j]==0 and checkimj[i-j+n-1]==0:
checkj[j]=1
checkipj[i+j]=1
checkimj[i-j+n-1]=1
Nqueen(i+1)
checkj[j]=0
checkipj[i+j]=0
checkimj[i-j+n-1]=0
Nqueen(0)
print(count)
# 여전히 오래걸림
# 생각해보니 2중for문일 필요가 없다
# n개를 놔야하니 한줄에 한개가 무조건 놓여야한다
# 한개 놨다면 다음줄에 무조건 놔야하는데 놓을곳이 없다면 더이상 탐색할 이유가 없다
# 그래도 아직 13,14는 종일 걸린다
# 어떻게 더 줄일까...
# 아무리 생각해도 더 줄일 방법이 없어서 pypy3으로 제출했다
# 된다 젠장