[프로그래머스] - N_Queen[파이썬]

그래프의 크기도 최대 12라고 생각해서 단순 2차원 배열 돌면서 모든 경우의 수를 구하는 DFS문제인지 알았더니

아주 띠용하는 방법이 있었다.

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

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

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

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

---

해설

사용되는 알고리즘 자체는 DFS가 맞다. 

하지만 2차원 배열로 공격가능한 모든 영역을 돌면서 가는것은 시간이 많이 든다.
따라서 이번 문제에서는 다음과 같은 개념을 가지고 1차원 배열을 활용하여 dfs를 한다. 

•  퀸이 있는 열과 행은 다른 퀸이 있을 수 없다.
• (x1,y1)과 (x2,y2)에 퀸이 있다고 했을때 |x1 - x2| == | y2 - y1| 일 경우는 서로의 공격 범위 안에 있다는 것이다.

이렇게 하며 서로 겹치는 범위를 판별하기가 쉬워진다. 같은 열과 행에 있으면 안되고 심지어 기울기까지 같으면 안된다.
예를 들어 다음 같은 경우를 보자 

 

(0, 1)에 퀸이 위치해 있을 경우 다음과 같이 그려진다.

x x x x           

x x x o    

o x o x 

o x o o

이때 새로운 후보퀸이 있을수 있는 열은 [0, 2, 3] 셋중 하나이다.
위의 그래프를 위로 밀어버리면 

arr = o x o o  이렇게 된다. 

그리고 x 대신에  현재 퀸의 행 값을 넣는다 그러면 다음과 같이 된다.

arr = o 0 o o 

예를 들어 arr[1] = 0이라 하면  1열 0행에 퀸을 위치한다는 소리이다.

 

dfs를 돈다고 가정 했을때 dfs의 depth를 열이라고 생각해보자

그러면 첫번째 dfs로 들어왔을때 depth는 0즉 0 열이 된다.

그러면 0열에 0행 1행 ... n행을 넣어보면서 조건을 만족시키는지 검사한다. 

그리고 나서 예를 들어  0열 0행이 조건을 만족 시켰고 

다음 dfs로 넘어가서 1열에 대해서 시도해보기 시작한다. 

arr = [0,0,0,0]

이상태에서 

1열 즉 arr[1]에 0행 부터  n행까지 넣어보면서 조건을 검사한다. 

이때 0행은 이미 0열이 차지 했으므로 넘어간다. 

그리고 1행부터는 만족시킨다. 

그러면 또 다음 dfs로 진입한다. 

 

이런식으로 만족하는 경우를 합하면 답이 나온다. 

 

def dfs(queen, n, row):
    count = 0

    if n == row:
        return 1

    # 행이 증가하는 방향으로 탐색
    for col in range(n):
        queen[row] = col

        #현재의 열까지 겹치는 경우가 있나 찾아봄
        for x in range(row):
            # 가로(행)로 겹치면 안됨
            if queen[x] == queen[row]:
                break

            # 대각선으로 겹치면 안됨
            if abs(queen[x] - queen[row]) == (row - x):
                break
        else:
            #열을 하나 추가시켜서 탐색
            count += dfs(queen, n, row + 1)

    return count


def solution(n):
    queen = [0] * n

    return dfs(queen, n, 0)