[프로그래머스 level3 N-Queen] 백트래킹 알고리즘 활용하기

해결해야하는 문제는 다음과 같았다.

https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

 

 

N-Queen 문제를 해결하기 전, 이 문제를 알고리즘 백트래킹 시간에 다루었던 기억이 나서, 백트래킹에 대해서 다시 짚어보았다.

백트래킹 알고리즘(Backtracking Algorithm)

가치지기 과정을 통해, 해를 찾아가면서 유망하지 않은 경우(non-promising)한 경우 그 경로를 더이상 탐색하지 않고 다른 경로를 탐색해나가는 방식이다.

즉, 유망하지 않다고 판단된다면 그 노드의 부모로 돌아가서 다음 자식 노드로 가는 방식으로 확인한다.

 

가지치기를 어떻게 하느냐에 따라 불필요한 경로를 삭제하는 가짓수가 달라지면서 경우의수가 달라진다.

 

 

책에서 제시된 수도 코드이다.

Foundations of Algorithms - Richard E. pg 267

 

이 수도코드를 바탕으로 아이디어를 정리하면 다음과 같다.

 

1. col을 정의한 후, 하나씩 검사를 시작할 것이다.

def solution(n):
    global answer
    answer = 0

    for i in range(n):
        col = [i] + [0]*(n-1)
        check(0,col)
    return answer

 

 

 

2. check 함수

def check(idx,col):
    global answer
    n=len(col)
    if promising(idx,col) :
        if idx==n-1:
            answer += 1
        else :
            for j in range(n):
                col[idx+1] = j
                check(idx+1,col)

 

3. promising 함수

def promising(idx,col):
    for k in range(idx):
        if (col[idx]==col[k]) or (abs(col[idx]-col[k])==idx-k) :
            return False
    return True

 

 

 

이러한 아이디어를 바탕으로 작성한 코드는 다음과 같다.

def check(idx,col):
    global answer
    n=len(col)
    if promising(idx,col) :
        if idx==n-1:
            answer += 1
        else :
            for j in range(n):
                col[idx+1] = j
                check(idx+1,col)


def promising(idx,col):
    for k in range(idx):
        if (col[idx]==col[k]) or (abs(col[idx]-col[k])==idx-k) :
            return False
    return True

def solution(n):
    global answer
    answer = 0

    for i in range(n):
        col = [i] + [0]*(n-1)
        check(0,col)
    return answer

 

 

문제 푸는 것도 중요하지만, 현재 알고리즘 지식들이 많이 머릿속에서 흐릿해져가고 있는 것 같다..

자료구조 및 알고리즘을 공부하며 그와 관련된 예시를 푸는 방식으로 공부를 해보는 것은 어떨까 라는 생각이 머릿속을 스치는 하루였다..

⭐️