N Queen

Backtracking 대표 문제

Backtracking 대표적 문제라고 한다.

지금은 일단 완전히 이해는 못하고 풀이 개념 정도만 간단하게 작성하고 다음에 다시 수정할 것이다.

single list shows rows and cols

single list 1개로 행과 열을 표현하는 방법이 중요하다.

list의 값은 열(col)을 표현하고
list의 index는 행(row)을 표현한다.

index 활용

downward diagonal 의 경우에는 2d list의 index의 합이 n과 같다.
(좌표 x,y일때 x+y = n)
upward diagonal 의 경우에는 2d list의 index의 차이가 모두 0으로 같다.
(좌표 x,y일때 x-y = 0)

DFS 풀이법

def check(queen, row):
    for i in range(row): # 가장 위부터 row까지 체크하면서 둘 수 있는지 알아낸다.
        # queen[i] 값과 queen[row] 값이 같다면,
        # i행의 값과 row행의 값이 같다면 같은 열이라는 뜻이기 때문에 퀸을 둘 수 없다.
        # queen[i] - queen[row] 값과 row - i가 같다면
        # 왼쪽 대각선으로 겹친다는 의미입니다.
        # queen[row] - queen[i] 값과 row - i가 같다면
        # 오른쪽 대각선으로 겹친다는 의미
        if queen[i] == queen[row] or abs(queen[i] - queen[row]) == row - i:
            return False
    return True

def search(queen, row):
    # stack = 1
    n = len(queen)
    count = 0

    if n == row: # 끝에 도달하면 1을 리턴한다.
        return 1

    for col in range(n):
        queen[row] = col # 내가 row, col 영역에 퀸을 뒀다 체크!
        if check(queen, row): # 둘 수 있는지 체크한다
            count += search(queen, row + 1) # 가능하다면 다음 행으로 이동!

    return count

def solution(n):
    # 1. 입력 부분 (시작점)
    # 2. 처리 부분 (경우의 수를 찾으면서 퀸을 둘 수 있는가?) 
    #     ㄴ 경우의 수를 모두 찾으면서 가능하지 않은것은 가지치기  <- 이것이 백트래킹
    # 3. 출력 부분 (가능한 경우의 수를 출력)

    return search([0] * n, 0) # queen을 둘 수 있는 배열을 만들고 시작점을 0부터 시작한다.