문제 : https://www.acmicpc.net/problem/9663

백트래킹 dfs 공부했다면 알만한 n-queen 문제이다. 사실 이 문제를 과거에 풀었지만 추후 비숍, 룩 문제도 풀면서 복습할겸 올려본다.

단순 dfs는 시간 및 메모리 초과 발생!

특정 조건없이 dfs를 해서 전체탐색을 한다면 메모리초과가 나는 것은 당연하다. 따라서 dfs할 때는 조건을 걸어 최대한 재귀함수를 덜 call할 수 있도록 만들어야 된다. 해당 문제에서는 queen이므로 가로, 세로, 대각선에 대해 조건문을 걸어주도록 한다

가로를 기준점으로

가로, 세로, 대각선 중 가로를 중심으로 탐색을 시작한다 생각하자. 그럼 세로와 대각선에 대해서만 걸러주면 되므로 조건문은 간단해지고, 따라서 dfs함수 구현도 간단해진다.

대각선 표현

1행 1열부터 n행 n열 까지 있다고 가정하자. 여기서 임의의 i,j를 선택하고 해당 점을 기준으로 X선을 그어보자. 그러면 선은 y=ax+b(x,y범위는 정수)로 그려질 것이고 접하는 점을 구하면 x=-b/(a+1), y=b/(a+1)가 된다. 즉, x+y=0라는 것이다. 이 성질을 이용하면 한 직선에서 i+j는 항상 같은 값을 가지고, 반대직선 같은경우 i-j는 항상 같은 값을 가진다. 따라서 위 성질을 이용해 대각선을 표현할 수 있다.

코드

answer = 0

def dfs(n,j,col,diago1,diago2):
    global answer
    if j==n:
        answer+=1
        return
    else:
        for i in range(n): # 가로
            if i not in col and i+j not in diago1 and i-j not in diago2:
                col.add(i)
                diago1.add(i+j)
                diago2.add(i-j)
                #print(j,i,col,diago1,diago2)
                dfs(n,j+1,col,diago1,diago2)
                col.remove(i)
                diago1.remove(i+j)
                diago2.remove(i-j)
                
                
                
            
n = int(input())
dfs(n,0,set(),set(),set())

        
print(answer)

결과