[Python] N Queen - JuyeolRyu/CodingTest GitHub Wiki

1. N-Queen

  • N X N의 체스판에서 퀸N개가 서로 공격할수 없도록 배치하는 경우의 수를 구하는 알고리즘입니다.
  • 같은 행,열,대각선에 다른 퀸이 없도록 배치해야 합니다.
  • 모든 경우의 수를 계산하면 시간이 너무 오래 걸리므로 백트래킹(Back-tracking) 방식으로 탐색해야 합니다.

2. N-Queen 풀이 과정

👉이미지 출처

(1) 가장 먼저 각 행에 몇번째 열에 퀸을 놓았는지 판단하기 위한 리스트를 생성해 dfs()메소드에 넣어줍니다.

#dfs(리스트,현재 행,n)
dfs([0]*n,0,n)

(2) 이 리스트와 DFS알고리즘을 사용하여 Queen을 놓을 위치를 탐색합니다.

(3-1) 만약 마지막 행까지 탐색했다면 탐색을 종료주는 예외처리를 합니다. (마지막행까지 탐색했을때 1개의 경우의 수가 생기므로 1을 반환합니다.)

if row == n:
    return 1

(3-2) 마지막 행이 아닌경우 현재 행 몇번째 열에 Queen을 배치할지 for문을 사용해 탐색합니다.

for col in range(n):
    queen[row] = col
    
    #배치가능한지 확인
    if is_valid(queen,row):    
        cnt+=dfs(queen,row+1,n)

(4) 이제 현재 배치한 행,열이 적합한 위치인지 판별해 줍니다.

for r in range(row):
    #같은 열에 위치한 퀸이 있는지 판단
    #같은 대각선 상에 퀸이 있는지 판단
    if queen[row] == queen[r] or abs(queen[row]-queen[r]) == row-r:
        return False
    return True

(5) 반환 결과가 True면 다음 행으로 진행하고 아니면 다른 열을 계속해서 탐색합니다.

3. N-Queen 코드

def is_valid(queen,row):
    for r in range(row):
        if queen[row] == queen[r] or abs(queen[row]-queen[r]) == row-r:
            return False
    return True
def dfs(queen,row,n):
    cnt = 0
    if row == n:
        return 1
    
    for col in range(n):
        queen[row] = col
        
        if is_valid(queen,row):    
            cnt+=dfs(queen,row+1,n)
    return cnt
def solution(n):
    return dfs([0]*n,0,n)

4. 관련 문제