프로그래머스 - [LEVEL 3] N-Queen

문제링크: https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

---

문제 설명

- 가로 세로가 n인 크기의 체스판에 n개의 queen을 놓을 수 있는 경우의 수

- queen은 가로 세로 대각선 이동이 가능

- n = 4 인경우 아래 이미지 처럼 2가지 경우의 수가 나옵니다.

---

풀이

- DFS / 백트래깅 (백트래킹은 지난 https://data-engineer.tistory.com/19에서 설명한 것 처럼 dfs에서 완전 탐색이 아닌 가지치기를 하며 탐색하는 것입니다.)

- nqueen은 유명한 문제라 그림까지 존재하네요!

- X친 항목들 처럼 퀸을 놓는게 불가능할경우 더이상 탐색하지 않고 바로 이전의 상태로 돌아가서 탐색하는 겁니다.

코드

def possible(x, y, n, col):
    for i in range(x):
        # 같은 열에 위치하는지 or 같은 대각선에 위치하는지 확인
        if y == col[i] or abs(y - col[i]) == x - i:
            return False
    return True

def queen(x, n, col):
    
    # row가 끝까지 갔으면 성공!
    if x == n:
        return 1
    
    count = 0
    
    for y in range(n):
        # 다음 퀸을 놓을 수 있는 경우만 진행
        if possible(x, y, n, col):
            col[x] = y # x번째 row의 col index 저장 ex) col[0] = 2 0번째 행의 2번째 col에 놓여져 있다.
            count += queen(x+1, n, col) # row index 증가 후 호출
            
    return count

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

    # 0은 세로축의 시작점 
    # n은 맵의 크기
    # col은 row 의 index를 담기 위한 리스트
    answer = queen(0, n, col)
    
    return answer

링크: https://github.com/smothly/Algorithm_Solving/blob/master/programmers-N-Queen.py