프로그래머스 Lv2 N-Queen (python)

N-Queen

풀이

재귀함수를 이용해줬다.
사실 예전에 자력으로 풀었었는데, 지금은 어떻게 풀어야하는지 잊어버려서 골골대다가 예전에 풀었던 것을 참고해서 풀었다.
많이 풀고 또 많이 풀고 또 많이 풀어서 예전 보다 더 좋은 실력을 가져야지.

1. 우선 프로그래머스는 함수형으로 문제를 풀어야되기 때문에 solution()밖에 변수를 설정한다.
2. soultion()에서 n을 받아옴과 동시에 global을 이용해서 설정한 변수의 값을 변경한다.
3. n queen을 재귀함수로 사용할 수 있는 함수를 따로 만들어주고, 이 때 맨 처음 만날 조건으로 row == n 즉, 모든 행에 다 퀸을 놓았으면 count +1 해주는 조건을 걸어주고 시작한다.
4. 그 외에는 각 행별로 열을 돌아가며, 퀸을 놓을 수 있는지를 판단, 된다면, 퀸을 놓은 후, 다음 행에서 퀸을 놓지 못하는 곳을 표시 한다. 그리고 n_queen(row+1, n)으로 들어간다.
5. 3,4를 반복하면서 함수가 완전히 종료되어서, solution()을 복귀하면 count를 반환시킨다.

# 열을 확인
check_col = []
queen = []
count = 0
# 대각선을 확인
# 우하 대각선
dial1 = []
# 좌하 대각선
dial2 = []

def n_queen(row, n):
    global check_col
    global count
    # row값이 n과 같다면 퀸이 서로 공격할 수 없는 판을 채운것이니, connt +1 해주고 return
    if row == n:
        count += 1
        return
    
    # 각 행별로 열을 돌면서 가능여부 확인하기
    for col in range(n):
        # 해당 열에 값이 없고, 각 대각선 라인을 사용할 수 있을 때 확인시키기
        if not check_col[col] and not dial1[row+col] and not dial2[row-col+n-1]:
            # 들어왔으니 퀸을 넣어보고, 이제 다음 행에 퀸을 못 넣는 곳들 표시하기
            check_col[col] = 1
            dial1[row+col] = 1
            dial2[row-col+n-1] = 1
            queen[row] = col
            # n_queen을 재귀함수 돌리기
            n_queen(row+1, n)
            # 빠져나왔으면 해당 자리는 0으로 만들고 재사용 가능하게 하기
            check_col[col] = 0
            dial1[row+col] = 0
            dial2[row-col+n-1] = 0

def solution(n):
    # n을 입력 받음에 따라 세팅해뒀던 변수를 조정.
    global check_col
    global queen
    global count
    global dial1
    global dial2

    check_col = [0] * n
    queen = [0] * n
    count = 0
    # 대각선은 행과 열의 합이 일정함을 이용하기 위한 dial
    dial1 = [0] * (2*n-1)
    dial2 = [0] * (2*n-1)
    # n_queen 함수 실행
    n_queen(0, n)
    return count
    # 대각선은 아래의 예와 유사하게 값을 가질 수 있으므로 dial을 이용
    #1 . . . 1
    # . 2 . 2 .
    # . . 3 3 .
    # . 4 4 . .
    # 5 5 . . .

다른 사람 풀이

나의 풀이법과 비슷하다고 판단된다. 좀 더 뜯어서 보도록해야겠다.

ans = 0
num = 0
chkX = [False for i in range(32)]
chkCross1 = [False for i in range(32)]
chkCross2 = [False for i in range(32)]

def nq(y, n):
    global ans
    x = 0
    if y > n:
        ans+=1
    for x in range(1, n+1):
        if chkX[x] or chkCross1[y + x] or chkCross2[(y - x) + n]:
            continue
        chkX[x] = True
        chkCross1[y + x] = True
        chkCross2[(y - x) + n] = True

        nq(y + 1, n)
        chkX[x] = False
        chkCross1[y + x] = False
        chkCross2[(y - x) + n] = False

def solution(n):
    nq(1, n)
    return ans

이건 무엇;;;;; 당황스럽다ㅋㅋㅋㅋㅋㅋㅋ

def solution(n):
    n_queen = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512, 95815104, 666090624, 4968057848, 39029188884, 314666222712, 2691008701644, 24233937684440, 227514171973736, 2207893435808352, 22317699616364044, 234907967154122528]
    return n_queen[n]