[Python][파이썬][프로그래머스] N-Queen(DFS/BFS)(백트레킹)

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

코딩테스트 연습 - N-Queen

 

문제 설명

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

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

 

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

제한사항

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

---

입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

---

▶ 문제설명

• DFS나 BFS를 써서 최적의 경우를 찾아나서야하는데, 조건이 유망하지 않다면 취소하고 다른 경우를 생각한다.
• 즉, 백트레킹을 해야한다.
• 퀸은 열 하나에 하나만 있어야 한다. 그렇지 않으면 공격범위에 들어온다.
• 따라서 아래와 같은 경우는 col = [2,4,1,3] 로 나타낼수 있다.
• 즉 인덱스가 행이고 값이 열인것이다.

조건1 : 같은 열 체크

• col[i] : i번째 행에서 퀸이 놓여있는 열의 위치
• col[k] : i번째 행에서 퀸이 놓여있는 열의 위치 
• col[i]가 col[k]와 같다면 유망하지 않은 것이다.

조건2 : 대각선 체크

• 왼쪽 퀸과의 열에서의 차이는 행의 차이와 같다. => col[i] - col[k] == i-k
• 오른쪽 퀸과 열에서의 차이는 행에서의 차이의 마이너스와 같다. => col[i] - col[k] == k-i
• 따라서 col[i] - col[k]의 절대값으로 대각선 조건을 체크한다.
• 이 조건으로 인하여 col은 [0]*(n+1)로 시작하는데 그 이유는 [0]*(n)으로 하면 1번째와 2번째가 바로 대각선 조건체크가 들어가기 때문이다. 이를 방지하기 위해 맨앞에 0을 추가한다. 

 

▶ 코드설명

def check(i, col):
    global answer
    n = len(col)-1
    if (promising(i, col)): # 조건 1과 2가 충족된다면 아래 코드를 실행한다.
        if i == n:
            answer += 1
        else:
            for j in range(1,n+1): #i와 j를 각각 1씩 늘려나가면서 가능한 조건을 찾는다.
                col[i+1] = j
                check(i+1, col)
                
def promising(i, col): # 조건1과 조건2를 체크할 함수
    for k in range(1,i):
        if (col[i] == col[k]) or (abs(col[i]-col[k]) == i-k):
            return False
    return True

def solution(n):
    global answer
    answer = 0
    
    col = [0]*(n+1)
    check(0,col)
    return answer