[BaekJoon] 백준 9663번 : N-Queen

9663번 : N-Queen

쉬워보이는 것 같으면서 엄청 어려웠던 문제였다..

백트래킹을 이용 해 다음 퀸이 올 자리가 올 수 없는 자리면 되돌아가 다시 작업 하는 방식으로 코딩을 하였다.

이런식으로 재귀를 통해 모든 가능성을 따져가면 된다..

[2020.12.31] 위 사진에서 (4, 3) 에서 (5, 5) 로 갈 수 없다 (0, 0) 에 놓여진 퀸 때문에 !

그런데 Python3 으로 제출을 하니까 시간초과가 발생했다.

아마 지금까지 방문했던 모든 좌표와 지금 방문해야 하는 좌표가 대각선 위치인지 파악을 하느라 그런 것 같다.

PyPy3 으로 제출하면 통과는 된다.

내일 할 일은 다른 문제를 푸는게 아니라 이 코드를 Python3 으로 제출했을 경우에도 통과하게 하는 것..

[2020.12.31] 도저히 개선방법이 생각이 안나 검색을 해보았는데 다른 풀이들도 파이썬으로 제출하면

시간초과가 발생한다고 한다.. 백트래킹 문제는 왠만하면 PyPy3 으로 제출하자..

---

def search(i, j, visitNode, visitCol):
	global res

	if i == (n - 1):
		res += 1
		return

	for col in range(n):
		if abs(j - col) >= 2 and col not in visitCol:
			check = 0
			for cur in visitNode:
				if abs(cur[0] - (i + 1)) == abs(cur[1] - col):
					check = 1
					break

			if check == 0:
				visitNode.append([i, j])
				visitCol.append(j)
				search(i + 1, col, visitNode, visitCol)
				visitNode.pop()
				visitCol.pop()
		else:
			continue


res = 0
n = int(input())
visitNode = []
visitCol = []

for j in range(n):
	search(0, j, visitNode, visitCol)

print(res)