[Programmers]Python_N-Queen

문제

 

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

Programmers

Programmers

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

 

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

코드

answer = 0
def isSafe(board, row, col): 
  # 왼쪽에 있는지 확인
    for i in range(col):
        if board[row][i] == 1: 
            return False
  # 왼쪽 위 대각선에 있는지 확인
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)): 
        if board[i][j] == 1: 
            return False
  # 왼쪽 아래 대각선에 있는지 확인
    for i, j in zip(range(row, len(board)), range(col, -1, -1)): 
        if board[i][j] == 1: 
            return False
    return True

def solve(figure, col):
    global answer
    #현재 column의 개수가 n(len(figure))개면 조건에 만족한 경우임
    if col == len(figure):
        answer += 1
        return
    
    #맨 왼쪽 column에서부터 맨 위 row부터 아래로 차례대로 확인
    for row in range(len(figure)):
        if isSafe(figure, row, col):
            figure[row][col] = 1
            solve(figure, col + 1) #재귀 호출
            figure[row][col] = 0 #0으로 다시 되돌린다음 다시 찾는다
    return answer
    
def solution(n):
    global answer
    figure = [[0] * n for _ in range(n)] #0으로 이루어진 체스판(격자)를 만든다
    answer = solve(figure, 0) #Column 0부터 시작하여 찾는다
    return answer

 

진행 과정

 

예제 #1

n = 4

 

[출처] http://ddmix.blogspot.kr/

위 그림을 보면 먼저 첫 번째 칼럼의 맨 위에있는 행부터 시작하는 부분부터 확인해야한다.

 

Queen이 1행 1열에 있을때 다음 칼럼(2열)에 Queen이 조건에 만족하는 위치를 찾아야한다.

여기서 위에서 작성한 코드 중 isSafe()함수를 확인해보자.

 

먼저 왼쪽에 Queen이 위치해있으면 안된다. 그리고 좌상, 좌하 대각선에 Queen이 위치해있으면 안된다. 이 3가지 조건을 만족해야 다음 칼럼에 위치시킬 수 있다. 이것이 isSafe()함수의 내용이다.

 

조건이 맞지않거나 조건이 맞아 다음 루트를 확인해보기 위해서 다음과같은 반복 재귀 호출을 사용한다.

for row in range(len(figure)):
        if isSafe(figure, row, col):
            figure[row][col] = 1
            solve(figure, col + 1)
            figure[row][col] = 0

 

조건에 계속 맞는다면 solve(figure, col + 1) 에서 figure[row][col] = 0으로 넘어가지 못할 것이다. 하지만 n개의 Queen이 모두 배치되면서 조건에 만족하게 되거나 조건에 맞지 않아서 다시 다른 루트로 되돌아가야한다면 figure[row][col] = 0으로 넘어가게된다.

 

figure[row][col] = 0으로 넘어가면 다른 루트로 갈 수 있는 지점까지 배치시킨 Queen을 0으로 초기화시킨다.