[Python - 프로그래머스 Level3] N-Queen

코딩테스트 연습 - N-Queen

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한 사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

입출력 예시

풀이 과정

백트래킹을 통해 퀸을 놓을 수 있는 모든 경우의 수를 검사해야하므로 DFS 문제라고 직감할 수 있었다. 하지만 퀸을 놓을 수 있는지 여부를 판단하는 방법에 생각해내는게 어려웠다. 혼자 고민해보다가 도저히 구현하지 못할거 같아 구글링을 해보았다.

 

고민해야 될 문제가 있다.

퀸을 놓을 수 있는 자리를 어떻게 알 수 있나?!

퀸을 어디에 놓을 수 있을지 검사할 수 있는 조건은 크게 3가지가있다.

1. Row가 겹치지 않는 곳

2. Column이 겹치지 않는 곳

3. 대각선이 겹치지 않는 곳 (↗︎,↘︎)방향

이것으로 queen을 놓을 수 있는 자리를 검사하면된다.

나는 퀸을 놓을 수 있는 자리를 검사하기 위해 row기준으로 dfs를 검사하므로 column이 겹치지 않는지, 대각선 (↗︎,↘︎)방향이 겹치지 않는지만 검사해주면 되었다. column 검사는 n 크기의 배열을 만들어서 구현해주면 되지만 대각선 검사는 규칙을 찾아야 한다.

아래 그림을 보면 이해가 조금 쉬울 것이다.

다음은 DFS를 구현하는 방법이다. 어떤 식으로 DFS가 시뮬레이션 될 지 고민하며 DFS함수를 짜야한다.

시뮬레이션 과정

1. 0번 째 줄에 말을 놓는다.
   1. (0,0)에 말을 놓고 상태를 업데이트한다.
      1. 1번째 줄에 말을 놓는다.
         1. (1,0) (1,1),(1,2)(1,3)를 차례로 검사하며 말을 놓을 수 있는 자리를 찾는다.
      2. 2번째 줄에 말을 놓는다.
         1. (2,0),(2,1) (2,2) (2,3)을 차례로 검사하며 말을 놓을 수 있는 자리를 찾는다.
      3. 3번째 줄에 말을 놓는다.
         1. (3,0) (3,1) (3,2) (3,3)을 차례로 검사하며 말을 놓을 수 있는 자리를 찾는다.
   2. (1,0)에 말을 놓고 상태를 업데이트한다.
   3. ...(3,0) 까지 반복

def solution(n):
    global answer
    answer = 0
    col = [True] * n
    diagonal1 = [True] * (2 * n - 1)
    diagonal2 = [True] * (2 * n - 1)

    def check_queen(x, y):
        return col[y] and diagonal1[x + y] and diagonal2[x - y + n - 1]

    def dfs(x):
        global answer
        if x == n:
            answer += 1
        else:
            for idx in range(n):
                if check_queen(x, idx):
                    col[idx] = False
                    diagonal1[x + idx] = False
                    diagonal2[x - idx + n - 1] = False
                    dfs(x + 1)
                    col[idx] = True
                    diagonal1[x + idx] = True
                    diagonal2[x - idx + n - 1] = True

    dfs(0)
    return answer