코딩 테스트(Python) n-queen

문제 설명

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

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

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

제한사항

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

 

def dfs(queen, n, row):
    # n x n 크기의 체스판에서 퀸을 배치할 수 있는 방법의 수를 반환하는 함수
    count = 0
    if n == row:  # 모든 퀸을 배치했다면
        return 1  # 1개의 valid solution을 찾았으므로 1을 반환
    
    # 각 행(row)에 대해 퀸을 배치할 열(col)을 찾는다
    for col in range(n):
        queen[row] = col  # 현재 행(row)의 퀸을 col에 배치
        
        # 이전에 배치된 퀸들과 충돌이 있는지 확인
        for x in range(row):
            # 같은 열에 퀸이 있다면 충돌
            if queen[x] == queen[row]:
                break
            
            # 대각선에 퀸이 있다면 충돌
            elif abs(queen[x] - queen[row]) == (row - x):
                break
        else:
            # 충돌이 없다면 다음 행(row)에 퀸을 배치하는 재귀 호출
            count += dfs(queen, n, row + 1)
    
    return count  # 유효한 배치의 경우를 반환

def solution(n):
    queen = [0] * n  # 퀸의 위치를 저장할 리스트 (각 인덱스는 행을 의미)
    
    return dfs(queen, n, 0)  # 첫 번째 행부터 시작하여 퀸 배치