leetcode.com 51. N-Queens

문제 링크: https://leetcode.com/problems/n-queens/description/

파이썬 소스: https://bit.ly/3vNf8d2

 

 백트래킹으로 풀 수 있는 문제로 잘 알려진, N-Queens 문제입니다. 이 문제에서 퀸(Queen)은 체스에서 Queen의 움직임과 동일한 움직임을 2차원 배열에서 할 수 있습니다. 즉, 전, 후 좌, 우 4방향에 추가로, 대각선 4가지 방향으로, 즉 8가지 방향으로 모두 움직일 수 있습니다. 다만 퀸을 이차원 배열에 배치할 때, 퀸과 퀸이 서로 공격할 수 없는 상태로 배치해야 합니다.

 N-Queens 문제는 N X N 배열에 N개의 퀸을 배치할 수 있는 모든 경우의 수를 찾는 문제입니다.

첫번째 퀸의 위치가 y, x, 두번째 퀸의 위치가 ny, nx 라고 한다면 아래 3가지가 성립해야, 두번째 퀸을 ny, nx 위치에 놓을 수 있습니다.

1. y != ny

2. x != nx

3. abs(y – ny) != abs(x – nx)

1번의 경우는 퀸이 위, 아래로 움직일 때, 서로 만나지 않는지 확인합니다.

2번의 경우는 퀸이 좌, 우로 움직일 때, 서로 만나지 않는지 확인합니다.

3번의 경우는 퀸이 대각선 4가지 방향으로, 서로 만나지 않는지 확인합니다.

추가로 3번에 대해서, 좀더 설명을 하자면, 기울기가 1 or -1인 직선에 2개의 퀸이 위치하는지 확인하는 것입니다. 기울기가 1 or -1이 아니라면, 2개의 퀸은 서로의 대각선 방향에 위치하지 않습니다.

좌표계의 관점에서는, 퀸의 좌표 [y, x], [ny, nx] 는 0, 0 좌표계에서 시작된 한 점이라고 볼 수 있습니다. 만약에 2개의 퀸의 좌표가 기울기가 1 or -1인 직선에 존재한다면, 아래 식은 1 or -1 입니다.

(y – ny) / (x – nx) = 1 or -1

우리가 알고자 하는 것은 한 직선에, 2개의 퀸이 존재하여, 두번째 퀸이 ny, nx 좌표에 존재할 수 없다는 것입니다. 그 직선의 기울기가 1이든 -1 이든 두번째 퀸이 그 ny, nx 좌표에 위치할 수 없습니다. 따라서, 기울기가 1일 때 만을 고려하여, 앞의 식을 좀더 단순하게 표현할 수 있습니다.

(y – ny) != (x – nx)

하지만, 기울기가 -1인 경우도, 고려해야 함으로, abs() 절대값 함수를 사용해서, 아래와 같이 바뀌게 됩니다.

abs(y – ny) != abs(x – nx)

 

이제 구현을 해보겠습니다.

board = [['.' for _ in range(n)] for _ in range(n)] answer = []

퀸을 배치할 2차원배열 board변수를 만들어주고, 결과를 저장할 answer 변수도 만들어 줍니다.

def attack(queens: List[List[int]], ny, nx):     for y, x in queens:         if y == ny or x == nx:             return True         if abs(y - ny) == abs(x - nx):             return True     return False

queens리스트에는 먼저 배치한 퀸들의 y, x좌표가 들어 있습니다. ny, nx는 새로 배치할 퀸의 위치입니다. 앞서 배치한 퀸들이 ny, nx에 위치한 퀸을 공격할 수 있는지 확인하는 함수입니다.

앞에서 설명한 1번 2번 규칙은 첫번째 if 문에 구현되어 있습니다.

3번째 규칙은 2번째 if 구현된 것을 볼 수 있습니다. 1, 2, 3번 모두에 해당되지 않으면, ny, nx위치가 공격을 받지 않는 다는 의미로, False를 리턴합니다.

def rec(board, y, queens, answer):     if y == n:         answer.append([''.join(row) for row in board])         return

재귀적으로 호출 될, rec 함수 입니다. 먼저 stop condition부터 알아보겠습니다.

y가 n과 같아지면, 즉 마지막 줄까지 퀸을 배치했으면, 퀸들이 배치되어 있는 board 변수를 저장합니다.

문제 풀이에 사용된 board 변수는 2차원 배열이고, 문제에서 답으로 리턴해야 하는 형태는 row 한줄이 1개의 스트링으로 표현된 형태 입니다.

리스트 answer에 넣기 전에, 한줄 row씩 꺼내서, 스트링으로 변환하고, answer에 넣어줍니다.

for x in range(n):     if False == attack(queens, y, x):         board[y][x] = 'Q'         rec(board, y + 1, queens + [[y, x]], answer)         board[y][x] = '.'

변수 y는 rec()함수의 인자로 받게 되구요, x 값이 for 루프 안에서 변하게 됩니다. y, x의 위치가, 기존의 퀸들의 위치(queens)로부터 공격을 받지 않으면, 퀸을 새로 배치합니다.

그리고, y를 1증가시켜서, 다음주에 퀸을 배치시키기 위해서, rec()를 재귀 호출 합니다.

 

위와 같은 방식으로 구현을 한 전체 코드는 아래와 같습니다.

from typing import List class Solution:     def solveNQueens(self, n: int) -> List[List[str]]:         board = [['.' for _ in range(n)] for _ in range(n)]         answer = []         def attack(queens: List[List[int]], ny, nx):             for y, x in queens:                 if y == ny or x == nx:                     return True                 if abs(y - ny) == abs(x - nx):                     return True             return False         def rec(board, y, queens, answer):             if y == n:                 answer.append([''.join(row) for row in board])                 return             for x in range(n):                 if False == attack(queens, y, x):                     board[y][x] = 'Q'                     rec(board, y + 1, queens + [[y, x]], answer)                     board[y][x] = '.'         rec(board, 0, [], answer)         return answer

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul