N-Queen - Python

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

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

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

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

입출력 예

문제해결과정

1. 몇시간을 고민해도 어떻게 푸는지 감이 안잡혀서 해설을 봤는데 해설마저도 이해가 잘 안갔다. 2차원배열로 구현해야하는것을 1차원배열로 구현해서 한다는것도 이해가 안갔다.. 그래서 해결하는데 엄청 오랜시간이 걸렸음에도 분명 얻은건 있다. 그래서 나름 뿌듯했다.

2. 그러면 2차원배열을 어떻게 1차원배열로 표시할까? -> 배열의 index를 행으로  배열의 값을 열로 계산한다.

3. Backtracking 시 방문하고 다음으로 탐색이 안되면 미방문 처리를 해야하는데 구지 안해도 되는 이유는 1차원배열이기 때문에 값이 덮어씌여진다.

4. 자세한 설명은 코드에 주석을 달아놓겠다.

---

def dfs(x, n, lst):
    answer = 0
    
    # 한칸씩 내려가면서 조건에 맞게 Queen을 배치시켰고 배열의 크기만큼 도달했을때
    if x == n:
        return 1

    for y in range(n):
        # 모든자리에 Queen을 두면서 배치가 가능한지 확인
        # 다음 행에 Queen를 위치할수있는지 확인
        lst[x] = y
        # 맨처음인 경우는 0,0 에 Q를 두면 다음행은 1,2에 두게 되는데
        # 그러면 2행, 3열에 Q를 둘수가 없게된다. 이때 BackTracking 을 하게 된다.
        # 재귀함수이기때문에 1,2에 뒀을때로 돌아가서 y를 증가시켜 다음가로에 한칸을 두고 
        # 다시 다음행부터 탐색해서 모든행에 조건에 맞게 들어가면 그때 answer +=1 을 한다.
        if check(x, y, lst):
            # 같은자리에 없으면서 대각선이 아니면 세로로 이동하면서 확인
            answer += dfs(x + 1, n, lst)

    return answer

def check(x, y, col):
    for i in range(x):
        if col[i] == y or abs(y - col[i]) == x - i:
            return False
    return True

def solution(n):
    return dfs(0, n, [0]*n)