[py] N-Queen

인증사진(2024-11-17)

 

문제

답

class NQueen:
    def __init__(self, size):
        self.size = size  // 체스판 크기
        self.solutions = [] // 리스트 생성
        self.col = [-1] * size   // 행에 배치된 퀸의 열을 기록하기 위한 초기화

    def solution(self):
        self.put_queen(0) 
        return self.solutions  

    def put_queen(self, row):
    
        if row == self.size:
            self.solutions.append(self.col[:])
        else:
            for col in range(self.size):
                if self.check_pos(row, col):  
                    self.col[row] = col  
                    self.put_queen(row + 1) 

    def check_pos(self, rows, col):
        for i in range(rows):
            if self.col[i] == col:
                return False
            if self.col[i] - i == col - rows: //왼쪽 대각선
                return False
            if self.col[i] + i == col + rows: //오른쪽 대각선
                return False
        return True
    
def solution(n):
    n_queen = NQueen(n)
    answer = n_queen.solution()
    return len(answer)

 

추가공부

 

이번 문제에서는 체스 판에서의 퀸의 성질을 아는 것이 중요하다. 같은 열과 각 대각선에 퀸이 놓여지면 안되는 것을 파악한 후, 백트래킹 방법으로 방향성을 잡는 것이 중요하다.