[리트코드] 51. N-Queens (Python) 백트래킹

N-Queens - LeetCode

문제

 퍼즐에서 퀸이 서로 공격하지 않도록 체스판 n위에 퀸을 배치하는 문제이다.

 

 

과정

• N*N 체스판에 N개의 퀸을 배치할 수 있는 경우의 수를 센다.
• 퀸은 상하좌우, 대각선 방향으로 거리 제한 없이 이동할 수 있다.
• N=8인 경우, 경우의 수는 다음과 같다.
        64 * 63 * ... * 57 = 178,462,987,637,760
        C 기준 1초에 1억 번을 연산하므로 모든 경우의 수를 탐색하는데 약 20.6시간이 소요된다.

 

1.  

백트래킹이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

최적화 문제와 결정 문제를 푸는 방법이 된다.

필요없는 경우를 가지치기(pruning)함으로써 시간복잡도를 줄이는 방법을 백트래킹이라고 한다.

 

입력

4

출력

[[".Q..","...Q","Q...","..Q."],["..Q.","Q.. .","...Q",".Q.."]]

 

풀이

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        visited = [-1] * n
        answers = []

        def is_ok_on(nth_row):
            for row in range(nth_row):
                if visited[nth_row] == visited[row] or nth_row - row == abs(visited[nth_row] - visited[row]):
                    return False
            return True

        def dfs(row):
            if row == n:
                grid = [['.'] * n for _ in range(n)]
                for idx, value in enumerate(visited):
                    grid[idx][value] = 'Q'
                result = []
                for row in grid:
                    result.append(''.join(row))
                answers.append(result)
                return

            for col in range(n):
                visited[row] = col
                if is_ok_on(row):
                    dfs(row + 1)

        dfs(0)
        return answers

 

한 줄씩 코드 해석해보기

visited = [-1] * n
answers = []

• n개의 개수만큼 visited에 -1로 만들어진 배열을 만든다. (-1은 아직 두지 않았다는 의미)
• vistited의 인덱스는 행, 값은 열을 나타낸다. ex) (1, 3)  놓은 경우, visited[1] = 3
• 정답을 반환할 answer 리스트를 만들어준다.

def is_ok_on(nth_row):
    for row in range(nth_row):
        if visited[nth_row] == visited[row] or nth_row - row == abs(visited[nth_row] - visited[row]):
            return False
    return True

• n번째 row에 퀸을 놓을 수 있는지 확인하는 함수 is_ok_on을 만들어준다.
• n번째 행의 퀸 위치와, 0번째 행부터 n번째행 -1 까지 놓여진 퀸의 위치를 비교한다.
• 방금 놓여진 nth 퀸은 (nth_row, visited[nth_row]) 에 놓여져있다.
• 각 행에 차례대로 단 한 번만 두기 때문에 행이 겹치는 것은 검사하지 않아도 된다.
• 1) 열 번호가 겹치지는 않는지? visited[nth_row] == visited[row]:
• 2) 또는 대각선으로 존재하지는 않는지? nth_row - row == abs(visited[nth_row] - visited[row]) 살펴본다.
• False와 True를 반환한다.

def dfs(row):
    if row == n:

• 백트래킹 함수 dfs를 만들어주고 row를 넣어준다.
• row 는 퀸을 놓을 행번호를 의미한다.
• dfs(0) 은 0번째 행에서 퀸의 위치를 고르는 것이고, dfs(1) 은 1번째 행에서 .. dfs(n-1) 은 n-1번째 행에서 퀸의 위치를 고르는 것이다.
• 따라서 row 는 n-1까지 가능하며, n이 되었다는 것은 n개의 퀸을 모두 올바른 위치에 두었다는 의미이다.
• 즉 row가 n이 되면 재귀탐색을 종료한다.

        grid = [['.'] * n for _ in range(n)]
        for idx, value in enumerate(visited):
            grid[idx][value] = 'Q'
        result = []
        for row in grid:
            result.append(''.join(row))
        answers.append(result)
        return

• grid리스트에 n개의 . 으로 이루어진 리스트를 만들어준다.
• visited에 저장된 값을 enumerate로 가져오며 grid 행과 열 위치에 Q를 추가해준다
• result 리스트에 grid의 행끼리 묶어서 추가해준다.
• answer에 result 값을 넣어준다

    for col in range(n):
        visited[row] = col
        if is_ok_on(row):
            dfs(row + 1)

• n개의 개수만큼 열을 확인한다.
• is_ok_on 함수를 통해 퀸의 위치를 확인 후 dfs함수를 통해 열에 추가해준다.

dfs(0)
return answers

• 처음 시작은 dfs(0) 으로 시작한다.
• answer을 반환한다.