[CLASS 4]백준 9663번 - N-Queen

9663번 : N-Queen

 

엄청 유명한 N-Queen문제이다. 이 문제는 시간 제한이 특이하게 10초이다. 그래서 파이썬으로도 가능할 줄 알았는데... 지금의 내 실력으로는 도저히 이거보다 빠른 코드를 작성하기가 힘들 것 같다...

 

내 코드:

# dawitblog.tistory.com
def find(r):
    global count
    if r == n:
        # n줄 까지 도달했다면 1가지 경우 추가
        count += 1
        return
    for c in range(n):
        # 대각선 값
        s = r + c
        b = r - c
        if col[c] and slash[s] and backSlash[b]:
            col[c] = slash[s] = backSlash[b] = False
            find(r+1)
            col[c] = slash[s] = backSlash[b] = True

n = int(input())
col = [True] * n
slash = [True] * (n*2+1)
backSlash = [True] * (n*2+1)
count = 0
find(0)
print(count)

 

이 문제를 풀기 위해 가장 중요한 생각은 당연히 해당 퀸을 어디에 배치해야 다른 퀸의 범위 바깥에 세울 수 있을지 이다.

 

첫 번째로, 퀸은 자신의 행은 모두 갈 수 있기 때문에 한 행에는 하나의 퀸이 무조건(NxN 판에 N개의 퀸을 배치해야 하므로) 있어야 한다.

이 생각을 바탕으로 해당 자리가 유효한지 검사할 때 행은 검사할 필요가 없다. 하나의 퀸을 배치하고 나서 다음 행으로 넘어가기 떄문에.

 

두 번째로, 대각선에 있는 퀸을 어떻게 구별할지에 대한 생각이다.

 

슬래쉬 모양(/)의 같은 대각선에 있는 칸들의 공통점은 r과 c의 합이 일정하다는 것이다 -> (2,0) / (1,1) / (0,2)

마찬가지로 역슬래쉬 모양(\)의 같은 대각선의 있는 칸들의 공통점은 r과 c의 차가 일정하다는 것이다.

 

또한 이러한 대각선들은 각각 2xn - 1개가 있다.

 

이 사실들을 이용해서 col , slash, backSlash 리스트를 만들어서 해당 선분 위의 칸이 현재 놓을 수 있는 곳인지 판단하면서 DFS를 시행하면 된다.