프로그래머스 Lv2 - N-queen(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/12952?language=python3

문제 설명

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

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

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

제한사항

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

입출력 예

문제풀이

포인트

• n x n 행렬이므로 2차원 배열을 사용하기 보다는, 1차원 배열의 인덱스 값과 value를 사용한다
• 퀸이 공격할 수 있는 범위는 같은 행, 같은 열, 그리고 각 위치에서 대각선에 있는 원소이다
  ex) (1, 2) -> (2, 3)
• 결국 한 행에 존재할 수 있는 퀸은 하나이다

def dfs(queen, n, row):
    count = 0
    
    if n == row:
        return 1
    
    # 각 행 진행
    for col in range(n):
        queen[row] = col
        
        # 각 열 진행
        # for - else 구문으로 break 걸리지 않으면 카운트 추가하고 다음 dfs 진행
        # break 걸리면 바로 다음 dfs 진행
        for i in range(row):
            # 한 열에는 하나만 있어야함
            if queen[i] == queen[row]:
                break
            # 대각선으로 겹치면 스킵
            if abs(queen[i] - queen[row]) == (row - i):
                break
        else:
            count += dfs(queen, n, row + 1)
    return count

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

• queen 배열에 같은 값이 있다면 break
• col값의 차이와 row값의 차이가 같다면 break
• 중간에 break되지 않은 경우 else로 넘어감