9663

날짜 : 2022. 10. 11

사용 언어 : python

 

문제

 

 

코드

import sys

def check(x): # 퀸과 만나는지 체크
    for i in range(x):
        if (col[x] == col[i]) or (abs(col[i] - col[x]) == (x - i)): # 각각 같은 행, 대각선 체크
            return False
    return True # 만나지 않을 때 True 리턴

def dfs(d):
    global cnt
    if d == n: # 전부 다 채웠으면
        cnt += 1 # 개수 증가
        print(col)
        return
    for i in range(n):
        col[d] = i
        if check(d): # 해당 자리의 적절 여부 체크
            dfs(d+1) # True라면 다음 자리 체크

n = int(sys.stdin.readline())
cnt = 0
col = [0] * n
dfs(0)
print(cnt)

 

 

알게된 점

- 2차원 배열로 일일이 소거하는 방식으로 풀이하려 했지만 시간이 너무 많이 걸렸다.

- 그래서 풀이방법 힌트를 위해 구글링을 했고 행 또는 열을 기준으로 하는 1차원 리스트를 만들어 dfs 방식으로 풀이해야 한다는 것을 깨달았다.

- check 함수의 if문을 이용해 같은 행을 체크하고(좌, 우), 대각선을 체크하여 이에 해당하면 False를 통해 가지치기를 했다.

- 그리고 따로 1부터 시작할 필요 없이 0부터 설정해서 풀이의 간결성을 높였다.

- 원리는 되게 간단한 것 같은데 이를 떠올리는 것이 꽤나 어렵게 느껴졌다.

- 특히나 재귀함수가 약한 나로서는 꽤나 많은 연습이 필요한 듯 보인다.

 

 

참고 사이트

- https://zidarn87.tistory.com/339

파이썬 / BOJ 백준 / 9663 N-Queen - 백트래킹