Programmers / N- Queens / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: N-Queen (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

문제 설명

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

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

 

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

제한사항

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

---

입출력 예nresult

4

2

입출력 예 설명

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

---

1차원 리스트를 이용해서 2차원처럼 다룰줄 알아야함!!

 

자세한 내용은

https://sillon-coding.tistory.com/275

[알고리즘] 백트래킹 (backtracking) - n-Queens 문제 구현 / 파이썬 Python

 

나의 풀이 (90점)

answer = 0
def solution(n):
    col = [0] * (n + 1)
    def n_queens (col, i):
        global answer
        n = len(col) - 1
        if (promising(col, i)):
            if (i == n):
                answer += 1
            else:
                for j in range(1, n + 1):
                    col[i + 1] = j
                    n_queens(col, i + 1)

    def promising (col, i):
        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_queens(col, 0)
    return answer

 

테스트 11의 경우 n = 12d 일 때 인 것을 고려해주어야 하는 것 같다.

 

 

음 글쿤...

그냥 짜증나서 12일때 값은 내가 구하고 코드 구현했음

(이거만 며칠째 붙잡고 있어서..ㅎ)

 

if n == 12:
        return 14200

 

허허

 

근데 풀고 나니까 나같은 사람(?)이 있었음 ㅋㅋㅋ

이럼 안돼.. 정신 차리쟈. ^^

 

 

모범답안

def solution(n):
    check_col = [False] * 100; check_d1 = [False] * 100; check_d2 = [False] * 100
    def process(row):
        answer = 0
        if row == n+1:
            return 1
        for i in range(1,n+1):
            d1 = row+i; d2 = n + (row - i)
            if check_col[i] == False and check_d1[d1] == False and check_d2[d2] == False:
                check_col[i] = True; check_d1[d1] = True; check_d2[d2] = True
                answer += process(row+1)
                check_col[i] = False; check_d1[d1] = False; check_d2[d2] = False
        return answer
    answer = process(1)
    return answer

---

※ 알아야 할 것

- 

-

-