03/28 코딩테스트 문제풀이 - 51. N-Queens (Leetcode) ⭐⭐⭐⭐⭐

문제

• Leetcode 알고리즘 문제
• 51. N-Queens (Hard)
• 문제 내용 : [링크]
  
  
  

---

내가 작성한 코드

class Solution:
    def solveNQueens(self, n):
        board = [["."]*n for _ in range(n)]
        result = []

        def is_valid(r, c):
            for k in range(n):
                if board[k][c] == "Q":
                    return False

                if board[r][k] == "Q":
                    return False

            i, j = r, c
            while i>=0 and j>=0:
                if board[i][j] == "Q":
                    return False
                i -=1
                j -=1

            i, j = r, c
            while i>=0 and j<n:
                if board[i][j] == "Q":
                    return False
                i -=1
                j +=1
            return True

        def backtrack(row):
            if row == n:
                result.append(["".join(row) for row in board])
                return

            for i in range(n):
                if is_valid(row, i):
                    board[row][i] = 'Q'
                    backtrack(row+1)
                    board[row][i] = '.'
        backtrack(0)
        return result

• (n x n) 체스판에 Queen 을 놓는 모든 경우의 수를 구하는 문제이다.
  이 때, Queen은 서로의 경로 상에 있으면 안 된다.

• board를 구현해준다. (추후 문자열 join하므로, 우선 칸별로 좌표)

• 해당 자리에 이전 Queen들이 새로운 Queen 경로 상에 존재하는 지 확인하는 is_valid(r,c) 함수를 구현해준다.

for문 안에서,

1. if board[k][c] == "Q"를 통해 세로(열)을 확인해준다.

2. if board[r][k] == "Q"를 통해 가로(행)을 확인해준다.

3. 왼쪽 위 대각선을 확인해준다.

4. 오른쪽 위 대각선을 확인해준다.

4가지 경우에 해당되지 않는다면True를 출력한다.

• 다음으로 backtrack(row) 함수를 구현해준다.

• row마다 n번의 반복을 해주면서, is_valid를 통해 해당 위치가 적합한 지 확인한다.

• 적합하다면, 해당 좌표의 값을 'Q'로 변경하고 backtrack(row+1)를 통해 재귀호출해준다. (다음 행으로 이동)

• 반복하면서, row==n인 경우, (즉 마지막 행인 경우) 각 행들의 값들을 하나의 문자열로 합쳐준 후, result에 append 해준다.

• 마지막 행까지 완성되지 않은 경우, 해당 좌표의 값을 원래의 값('.')으로 복구해준다.

• result를 return 한다.

---

⭐⭐⭐⭐⭐

1. is_valid함수를 통해 적합성 확인 후 재귀함수를 전달한다.

2. result.append(["".join(row) for row in board])를 통해 문자열을 합친 후 append 해줄 수 있다.