[BOJ][Python]백준 9663번 풀이

그냥 듀크입니다. 이번 문제는 진짜 오래걸렸는데요. 머리로는 알겠는데 재귀로 구현을 하려니 자꾸 뭐가 안되고 해서 시간이 많이 걸렸습니다. 제가 재귀 연습을 좀 해야겠다 하고 생각하게 해준 문제기도 하구요.

 

문제 링크 : https://www.acmicpc.net/problem/9663

9663번: N-Queen

코드 : 

import sys
ssr = sys.stdin.readline

def put_queen(cdx):
    if cdx == n:
        global cnt
        cnt += 1
    else:
        for i in range(n):
            if visited[i]:
                continue
            q_list[cdx] = i
            if check(cdx):
                visited[i] = True
                put_queen(cdx+1)
                visited[i] = False
            
def check(n):
    for i in range(n):
        if q_list[n] == q_list[i] or n-i == abs(q_list[n] - q_list[i]):
            return False
    return True
                
if __name__ == '__main__':
    n = int(ssr())
    cnt = 0
    q_list = [0 for _ in range(n)]
    visited = [False for _ in range(n)]
    
    put_queen(0)
    print(cnt)

참고로 말씀을 드리자면 파이썬은 pypy3로 제출하셔야 통과 될 겁니다. 기본적인 개념은 일단 퀸을 한 번 놔보고 check 함수에서 조건에 부합하는지를 확인한 다음 문제가 없으면 진행하고 문제가 있으면 인덱스를 올려가면서 해당 사이클을 반복하는 형식입니다. 미리 queen을 배치할 보드를 만들어놔야 인덱스에러가 뜨지 않습니다.

 

그냥 듀크였습니다.