[Python] 백준 3344 - N-Queen

https://www.acmicpc.net/problem/3344

 

문제

8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다. 퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다.

이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다.

N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇 가지가 있을까?

이 문제는 N>3인 경우에 경우의 수가 적어도 1개 라는 것이 증명되어 있다. 예를 들어, N=26인 경우에 22317699616364044가지 방법이 있다.

N이 주어졌을 때, N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 한가지 경우를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 8, 26, 213, 2012, 99991, 99999중 하나이다.

 

출력

N개의 줄을 출력해야 한다. i번째 줄에는 하나의 정수를 출력해야 하고, 이 정수는 i번째 행에 있는 퀸이 있는 열의 번호이다.

 

---

 

풀이

 

이거 졸라 재미있는 문제이다.

 

보통 N-Queen 문제는 백트래킹으로 일일이 카운팅한다. 그래서, N이 16까지만 가도 기하급수적으로 시간이 오래 걸린다.

이번 문제는 N이 주어졌을 때 가능한 경우의 수를 구하는 것이 아니라, 실제로 해를 한 개 찾아서 출력해야 한다.

다만, N이 무지막지하게 크다는 것이 문제점이다.

해를 구성하는 문제이므로 내 개인 환경에서 주어진 N(8, 26, 213, 2012, 99991, 99999)들에 대해서 해를 찾고 코드는 그냥 이걸 출력하기만 하면 될 것이다.

그러기 위해서 먼저, 오늘 우리에게 큰 도움이 되어줄 예전에 푼 백준 9663 문제의 코드를 소개한다.

N = int(input())
cnt = 0

col = [False]*N
diag1 = [False]*(2*N-1)
diag2 = [False]*(2*N-1)

def search(y):
    global cnt
    if y == N:
        cnt += 1
        return

    for x in range(N):
        if col[x] or diag1[x+y] or diag2[x-y+N-1]:
            continue
        col[x] = True
        diag1[x+y] = True
        diag2[x-y+N-1] = True
        search(y+1)
        col[x] = False
        diag1[x + y] = False
        diag2[x - y + N - 1] = False

search(0)
print(cnt)

 

이 코드를 조금 수정하면, 해들을 쭉 구할 수 있다.

N = int(input())
cnt = 0

col = [False]*N
diag1 = [False]*(2*N-1)
diag2 = [False]*(2*N-1)

ans = [0]*N

def search(y):
    global cnt
    if y == N:
        cnt += 1
        print(ans)
        return

    for x in range(N):
        if col[x] or diag1[x+y] or diag2[x-y+N-1]:
            continue
        col[x] = True
        diag1[x+y] = True
        diag2[x-y+N-1] = True
        ans[y] = x
        search(y+1)
        ans[y] = 0
        col[x] = False
        diag1[x + y] = False
        diag2[x - y + N - 1] = False

search(0)
print(cnt)

 

일단 여기에 N = 26만 넣고 돌려도 코드가 끝이 안난다.

그래서 우리는 N이 작은 경우에 대해서 코드를 돌려 좋은 해를 몇 개 찾아보고 거기서 규칙을 찾을 것이다.

 

일단 N = 4, 5, 6, 7일 때 코드를 돌려보면 눈에 띄게 예쁜 형태의 해가 있다.

N = 4

N = 5

N = 6

N = 7

 

사진에서는 해가 너무 많아 초기 몇 개만 잘라서 출력한 것이다.

그런데, 맨 위 해들을 보자. 너무 규칙적이고 아름답지 않은가?

 

이를 그림으로 나타내면 다음과 같다.

 

 

하지만 이 아름다운 규칙은 아쉽게도 N = 8에서 끊겨버리고 만다.

 

그리고 코드를 돌려보면 N = 9에서도 안되는 것을 볼 수 있다.

 

그러면 일단 N이 홀수 일 때 경우를 나눠서 생각해보자.

 

N이 홀수일때

코드를 돌려보면 아름다운 패턴은 다음과 같은 경우에 나타난다.

N = 5, 7, 11, 13, 17, 19 ...

여기서 우리는 N이 3의 배수일 때에는 규칙이 적용 안됨을 알 수 있다.

 

여기서 알 수 있는 한가지: 우리는 N = 99991일 때의 해를 구했다!!

 

for i in range(0, N, 2):
    print(i+1)
for i in range(1, N, 2):
    print(i+1)

 

근데 아쉽게도 주어진 N중 홀수는 99991을 빼면 전부 3의 배수이기 때문에 그 경우에 대해서도 해를 찾긴 찾아야 할 것이다.

 

 

N이 3의 배수일 때의 규칙을 찾기 해서 N = 9, 15, 21, 27일때를 봐야하지만 코드를 다 돌리기에는 수가 너무 크다. 그래서 일단 N = 9일때 해를 쭉 돌려보도록 하자.

 

N = 9(일부분)

 다른 수많은 해들을 제치고 저 [2, 0, 8, 6, 4, 1, 7, 5, 3]이라는 해가 눈에 들어온다. 이 해를 그림으로 표현하면 다음과 같다.

 

形가 뭔가 아름답다.

아름다운 모양이다. 혹시 이와 비슷한 해를 N = 15에서도 발견할 수 있지 않을까?

 

N = 15일 때 코드를 다 돌리기에는 너무 시간이 오래 걸리니까 코드를 조금 수정해서 2, 0으로 시작하는 해를 찾아보자.

 

수정된 코드

 

그리고 약 10초정도가 지나면 2, 0으로 시작하는 해들을 쭉 얻을 수 있다.

찾았다!

 

N =15 에서도 똑같은 형태의 해를 찾을 수 있었다.

 

귀납적으로 우리는 N이 홀수이고 3의 배수일 때 저런 형태의 해를 가진다는 것을 생각해볼 수 있다.

 

그러면 우리는 N = 213, 99999 일때의 해를 구한 것이다!

 

if N%3 == 0: #213, 99999
    print(3)
    print(1)
    for i in range(N-1, 3, -2):
        print(i+1)
    print(2)
    for i in range(N-2, 2, -2):
        print(i+1)

N이 짝수일때

 

남은 경우는 N = 8, 26, 2012이다.

우리가 이 글 맨 위에서 찾은 아름다운 규칙은 N이 짝수일 때도 적용될까? 한번 쭉 그려보자.

 

 

8은 안된다(위에서 보긴 했지만). 그리고 쭉 해보면 대각선이 겹치는 것 때문에 N = 8, 14, 20, 26....인 경우, 즉 3으로 나눈 나머지가 2인 경우는 모두 간단한 규칙이 적용되지 않음을 알 수 있다.

 

그리고 매우 슬프게도 남은 테스트케이스인 8, 26, 2012는 모두 3으로 나눈 나머지가 2이다.

 

N = 8일때 코드를 돌려서 예쁜 형태의 해가 뭐가 있는지 찾아보도록 하자.

 

これ、뭔가 좀 綺麗하다.

1, 3, 5, 7, 2, 0, 6, 4라는 뭔가 아름다운 해가 하나 눈에 들어온다. 이는 그림으로 표현하면 아래와 같다.

 

비슷한 형태를 N = 14일때 찾을 수 있을까?

 

N = 14

그리고 똑같은 형태를 N = 20일때도 찾을 수 있다.

 

이를 그림으로 그려보았다.

 

홀수는 쭉 내려가고

짝수는 처음에는 두 번 올라가고 맨 밑까지 한 번 쭉 떨어졌다가 다시 쭉 내려오는 규칙이다.

 

좋다! N = 8, 26, 2012일 때도 해를 구했다.

 

if N%2 == 0: #8, 26, 2012
    if N%3 == 2:
        for i in range(1, N, 2):
            print(i+1)
        print(3)
        print(1)
        for i in range(6, N, 2):
            print(i+1)
        print(5)

 

 

최종 코드

위에서 찾은 규칙들을 모두 코드로 모아보면, 최종 정답이 나온다.

N = int(input())

if N%2 == 0: #8, 26, 2012
    if N%3 == 2:
        for i in range(1, N, 2):
            print(i+1)
        print(3)
        print(1)
        for i in range(6, N, 2):
            print(i+1)
        print(5)

else:
    if N%3 == 0: #213, 99999
        print(3)
        print(1)
        for i in range(N-1, 3, -2):
            print(i+1)
        print(2)
        for i in range(N-2, 2, -2):
            print(i+1)
    else: #99991:
        for i in range(0, N, 2):
            print(i+1)
        for i in range(1, N, 2):
            print(i+1)

 

 

그리고 놀랍게도 AC가 나온다.

 

한 40분만에 풀었다(처음에 틀린거는 다 잘 구해놓고 인덱스 1 안올려서....)