[백준] 9663 N-Queen

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

전형적인 N-Queen 문제로 완전 탐색, 백트래킹 사용

2) 알고리즘

• 완전 탐색
• 백트래킹

3) 풀이 코드

사용 언어 - Python

import sys


def chk(y, x):
    for i in range(1, y+1):         
        if x - i >= 0 and cols_selected[x] - i == cols_selected[x-i]:       # 현재 열의 행과 옆에 떨어진 열의 행이 같을때
           return False                                                     # 위로 올라갈수록 대각선에 퀸이 있을때
        elif x + i < N and cols_selected[x] - i == cols_selected[x+i]:
            return False
    return True

def solution(n):
    global answer

    if n >= N:              # 모든 행에 놓았으면 정답 개수 증가
        answer += 1
        return

    for c in range(N):
        if cols_selected[c] == -1:          # 열에 퀸이 놓여있지 않으면
            if chk(n, c):                   # 위에 행 중 대각선에 퀸이 없을때
                cols_selected[c] = n        # 지금 열에 행 번호 저장
                solution(n+1)               # 다음 행 탐색
                cols_selected[c] = -1

N = int(sys.stdin.readline())               # 체스판의 크기
cols_selected = [-1] * N                    # 열에 퀸이 놓였는지 유무 판별 및 몇번 행에 놓였는지 저장
answer = 0                                  # 정답을 저장할 변수

solution(0)                                 # 0번 행부터 시작

print(answer)                               # 출력

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

Python 으로 제출시 시간초과가 발생

PyPy3 로 제출하여 통과, Python 으로 통과할 방법을 찾아보았지만 문제에서 N의 최댓값이 너무 커서 방안을 찾기 어려움

2) 새롭게 학습한 내용

시간초과를 해결하기 위해 많은 노력이 필요함

---

🔗 문제 링크

- https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다