프로그래머스 12952 - N-Queen

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

코딩테스트 연습 - N-Queen

문제 설명 - 백트래킹

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

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

 

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

제한사항

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

---

문제 풀이

https://chanhuiseok.github.io/posts/algo-23/

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

백트래킹에 대한 설명은 위의 사이트에 잘 나와있다.

N-Queen은 백트래킹에 아주 대표적인 문제로 그림까지 많이 있다.

1. 첫번째 줄 첫번째 칸에 Queen을 배치
2. 다음 Column으로 이동해서 row마다 놓을 수 있는지 판별
3. 판별했을 때 놓을 수 없는 경우는 거기서 끝을 내고 다른 경우의 수를 판별함

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

def queen(col, idx):
    #모든 row를 다 체크했으면 종료
    if idx == len(col):
        return 1
    
    count = 0
    for y in range(len(col)):
        if(check(col, idx, y)):
            col[idx] = y
            count += queen(col, idx + 1)
    
    return count

def solution(n):
    col = [0] * n
    return queen(col, 0)

코드는 굉장히 간단하지만 어렵다...

특히 재귀가 좀 많이 되다보니 많이 파고 들어가야한다.

 

이해가 안되면 표를 그리면서 계속 따라가면서 보는것도 나쁘지 않다.