🥇[백준] 9663 N-Queen (골드4) / 백트래킹, 룩업테이블

문제요약

나의 코드 및 설명

 

• 문제를 해결하기 위해 규칙을 먼저 찾아야 한다. y축을 i, x축을 j 라고 했을 때, 대각선 위로 향하는 좌표들의 i,j 값을 빼보면 모두 같다는 것을 알 수 있다. 또 대각선 아래로 향하는 좌표들의 i,j 값을 더해보면 값이 모두 같다는 것을 알 수 있다.
• 이 규칙을 활용하여, v[i+j], v[i-j] 의 값을 저장해주기 위한 룩업테이블을 만든다. 예를들어 i-j = -1 이라면, v[-1] 에 1을 저장한다. 이렇게되면, 오른쪽 위로 향하는 대각선의 좌표들은 모두 방문처리가 된다.
• 현재 좌표의 방문 처리를 위한 v1 리스트, 오른쪽 대각선 아래(\)로 향하는 좌표들의 방문 처리를 위한 v2 리스트, 오른쪽 대각선 위(/)로 향하는 좌표들의 방문 처리를 위한 v3 리스트를 메인 함수에 초기화 해준다.
• 그리고 dfs를 처리하며 x, y 좌표가 지정될 때마다 v1, v2, v3의 리스트에 해당 좌표에 해당하는 인덱스에 1을 저장한다.
• 하위 dfs를 호출하면서, 이미 v1, v2, v3의 리스트의 좌표의 인덱스에 해당하는 값이 1이라면, 방문이 불가하므로 다음 for문을 수행하고, for문을 다 돌았는데도 하위 함수를 호출하지 못한다면, 상위 함수로 돌아와 좌표에 해당하는 v1, v2, v3의 값에 0을 저장한다.

def dfs(y):
    global ans
    if y == n:
        ans += 1
        return
    for i in range(n):
        if v1[i] == 0 and v2[y+i] == 0 and v3[y-i] == 0:
            v1[i] = v2[y+i] = v3[y-i] = 1
            dfs(y+1)
            v1[i] = v2[y+i] = v3[y-i] = 0
    

n = int(input())
ans = 0
v1 = [0] * n 
v2 = [0] * (2*n)
v3 = [0] * (2*n)

dfs(0)
print(ans)

피드백

하.. 너무 어렵다.. ㅠ 충분히 풀 수 있을거라 생각했는데 뜻대로 되지 않았다.. 룩업테이블을 활용하는 것에 더 진심이어야겠다. 문제를 풀기 전 어떻게 문제를 해결할 수 있을지 더 창의적으로 생각해보고 구현해봐야겠다.