🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]9663번 - N-Queen

9663번 - N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92


해결할 방법을 생각해보자.💡

최근에 도전한 알고리즘 문제 중에서 가장 어려운 것 같다.

아무리 방법을 생각해봐도 문제를 풀지 못해서 다른 분들의 블로그를 보고 풀이를 이해하였다… ㅠㅠㅠ

체스에서 퀸은 상하좌우대각으로 몇칸이든 이동해서 다른 말들을 잡을 수 있다.

따라서 자신의 위치에서 8방향으로 갈 수 있는 위치에 퀸들이 위치하면 안되는 것이다.

예를 들어서 N = 4일 때 체스판에서 퀸이 4개 놓일 수 없는 경우를 표현해봤다. KakaoTalk_Photo_2022-08-14-16-09-44

다음은 되는 경우를 표현해봤다.

KakaoTalk_Photo_2022-08-14-16-09-49

차이점은 기존에 놓여있는 행에도 놓여있지 않고, 그 체스들의 대각에도 걸리지 않는 것이다.

이로써, 이 문제의 가장 중요한 점은 3가지이다.

  1. 각 열에 하나의 퀸을 놓되 행 중복 X
  2. 대각에 위치하면 안된다.
  3. N개의 퀸을 모두 놓아야 함

여기까지는 이해했지만 그 내용을 이용해 코드를 짜는 것에는 하루종일 생각해봐도 한계를 느껴 다른 분들의 풀이를 읽어보게 되었다.(흑)

다른 분들의 풀이를 보면 이전 열에 같은 행과 대각선에 위치하는지 확인하는 함수 하나와 퀸을 놓는 재귀를 사용한 함수를 사용해서 대부분 풀으셨다.

하지만, 이 문제의 N이 15까지 주어지므로 풀으셨던 방법들 모두가 시간초과에 걸리게 된다는 점을 알게 되었고, pypy를 사용했다는 것도 알았다.(여기서 파이썬의 느림의 한계를 느끼셨다고들 한다.)

그래서 또 여러가지 찾아보던 중에 인덱스의 합을 사용해서 문제를 푸시는 분의 글을 보았다. https://developmentdiary.tistory.com/292

이런 생각을 어떻게 하는지 정말 신기하다..

밑에 올리는 코드는 위의 주소에서 가져온 코드로 참고 정도만 해주시길 바란다.

나중에 실력쌓고 다른 언어로 도전해봐야겠다 ㅠㅠ

코드 💻

n, ans = int(input()), 0
a, b, c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)

def solve(i):
    global ans
    if i == n:
        ans += 1
        return
    for j in range(n):
        if not (a[j] or b[i+j] or c[i-j+n-1]):
            a[j] = b[i+j] = c[i-j+n-1] = True
            solve(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False

solve(0)
print(ans)
출처: https://rebas.kr/761 [PROJECT REBAS:티스토리]

해결 로그

문제 푼 날짜 체크
2022-08-16 ✔
   
   
   
   

2022

[web]jQuery 복습 3

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 2

13 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 1

14 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리4

5 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리3

10 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리2

7 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리1

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]CSS 기초 정리

11 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]HTML 기초 정리

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[Pandas]pandas 연습

3 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑

2021

[Python기초]module

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑