너무나도 유명한 대표적인 backtracking 문제 N-Queen 문제이다.
처음엔 체스판인 이차원 배열 board
를 만들어 갈 수 있는 곳을 marking하면서 해결하려했으나 n이 커질수록 board
를 생성하는데 걸리는 시간이 커져 효율성에서 실패하였다.
그래서 좀 더 효율적으로 코드를 작성하기 위해 고민해보았다. 그 결과 일차원 배열만으로도 같은 열에 있는 말을 체크할 수 있고, 수학적으로 대각선상에 말이 위치할 수 있는 방법이 있다는 것을 알게 되었다. 방법은 다음과 같다.
마지막으로 같은 행에 대한 체크는 재귀적으로 다음 깊이로 넘어갈 때 행을 +1씩 증가시켜 같은 행에 위치하지 않는다는 것이 보장되므로 굳이 따로 체크하지 않아도 된다.
def solution(n):
global answer
answer = 0
def search(k, board):
global answer
if k == n:
answer += 1
else:
for i in range(n):
tmp_board = board[::]
for r, c in tmp_board:
if i == c or abs(k-r) == abs(i-c):
break
else:
tmp_board.append((k, i))
search(k+1, tmp_board)
search(0, [])
return answer
다른 사람의 풀이를 보니 행, 열, 대각선 각각을 체크할 수 있는 일차원 배열 3개를 만들어 더 효율적으로 푸는 방법도 있던 것 같은데 참고해봐야겠다.