9663 문제 python N-Queen [백준-골드4/백트래킹]

문제 내용 요약

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

문제 원리파악

백트래킹 문제인 만큼 어떻게 백트래킹 되는지 방식을 알아야 된다.

재귀함수 활용한 DFS 탐색 방식

def Back_Track(count, col, i):
	if count == 0: # 재귀함수를 돌면서 0일때 종료됨
    	break
        
    count -= 1
    
    # 트리로 따지면 가장 안쪽으로 탐색하는 방식
    for j in range(1,5):
    	col[i] = j
        Back_Track(count, col, i+1)
        

col = [0,0,0,0,0]
Back_Track(5, col, 0)

문제풀이에 사용되는 For문안의 재귀함수의 흐름이나 방식을 이해하는게 먼저라고 생각했다.

직접 코드를 짜보고 분석해보니 재귀함수안의 조건식(Count==0)이 될 때까지 함수를 계속 반복하고 그 이후에 For문을 실행했다..뭔가 응용하려하니 꾀나 복잡했던거 같다.

 

문제풀이

재귀함수 시작전에 놓을 위치에 있는 퀸이 같은 열에 있을 경우(조건1) or 대각선에 위치에 있을 경우(조건2) 퀸을 다음 순서의 퀸을 놓는 것이 아니라 현재 퀸의 위치(열)를 바꿔가며 조건에 해당되지 않는 위치를 찾음

 # Promising가 True일 경우 다음 인덱스 값을 올리고 재귀함수를 실행하고 -> 새로운 퀸을 놓는다는 의미,
 # Promising가 False일 경우 이전 함수의 For문이 돌아가며 값이 바뀜 -> 현재 퀸의 열의 위치를 바꿔가며 조건에 맞는 자리를 찾는 다는 의미 

def n_queens(i, col):

    n = len(col) - 1
    
    # Promising가 True일 경우 다음 인덱스 값을 올리고 재귀함수를 실행하고 -> 새로운 퀸을 놓는다는 의미,
    # Promising가 False일 경우 이전 함수의 For문이 돌아가며 값이 바뀜 -> 현재 퀸의 열의 위치를 바꿔가며 조건에 맞는 자리를 찾는 다는 의미 
    if (promising(i, col)): # 위치가 열이 겹치거나, 대각선일 경우 False
        if (i == n): # Promising 한데 말을 다 놓으면 4==4이면 끝
            print(col[1: n+1])
        else:
            for j in range(1, n + 1):
                    col[i + 1] = j
                    print(col)
                    n_queens(i + 1, col)
                    
def promising(i,col):
    k = 1
    flag = True
    while(k < i and flag):
        if(col[i] == col[k] or abs(col[i] - col[k]) == (i-k)):
            flag = False
        k += 1
    return flag


n = 4
col = [0] * (n+1)

n_queens(0, col)

깨달은점

재귀함수를 통해 역으로 탐색하며 이러한 방식으로도 풀 수 있다는 것을 알았다. N-Queen 문제에서 다른 풀이들이 대부분 2차원 배열을 1차원 배열로 줄여서 생각하다보니 내부 구조가 어떻게 되는지 분석하려고 했던 나는 더 헷갈렸던거 같다..

 

그리고, 백트래킹 문제가 어려운 문제측에 속한거 같아서 이러한 방식의 문제를 추가적으로 풀어봐야지 좀 더 접근할 수 있는 방법이 생각날 것같다. 현재 이 문제만으로는 많이 부족한거 같다.