[백준/3344] N-Queen (Python)

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

3344번: N-Queen

 

Difficulty : Platinum 2

 

Status : Not Solved

 

Time : ??:??:??

 

---

 

문제 설명

 

 

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번째 행에 있는 퀸이 있는 열의 번호이다.

 

입력 예시

 

8

 

출력 예시

 

3
6
8
1
4
7
5
2

 

 

---

 

풀이

 

왜 플래티넘 2이 붙었지...? 싶었는데, 조금 기분나쁜 문제였다. 이 문제를 풀기 위해서 요구되는 지식이 매우 특정적이고, 이를 즉석에서 생각해내기란 쉽지 않다. 아마 아이디어를 생각해낼 난이도 자체는 매우 높으나(논문으로도 발표되었던 특정 해 구하기 방법이므로), 이를 구현하는 것은 매우 쉬우므로 이 정도 난이도를 받게 된 것 같다.

 

맨 첫 번째 접근은 나이트의 행마를 생각해낸 것이다. 퀸 이동은 가로 - 세로 - 대각선으로 가능하므로, 퀸에서 가로, 세로가 1칸, 2칸 차이가 나는 나이트 행마는 퀸의 이동 가능 칸에 포함되지 않는다. 즉 약 N // 2 개의 퀸을 나이트를 배치하듯 배치하면 된다. 우선 2번째 칸부터 2칸씩 띄엄띄엄 배치하고, 끝까지 도달하면 1번째 칸부터 다시 2칸씩 띄워서 배치한다.

 

	Q
			Q
Q
		Q

 

 

이를테면 이렇게. 대부분의 경우는 잘 동작했지만, wa를 내놓는 걸 확인했다. 아마 특정 상황에서는 잘 동작하지 않는 것 같은데, 우리가 테스트해봄직한 낮은 N값에서는 잘 동작함을 확인했기에... 헤메기 시작했다.

 

결국 못참고 구글링에 손을 댄 결과, 다음 식을 발견하기에 이른다.

https://en.wikipedia.org/wiki/Eight_queens_puzzle#cite_note-bernhardsson-5

Eight queens puzzle - Wikipedia

 

한국어로 요약하면 다음과 같다.

• 보드판 크기를 N이라 두자.
• N을 6으로 나눈 나머지가 2 또는 3이 아니라면, 1부터 N까지의 수를 (짝수 오름차순) + (홀수 오름차순)으로 나열하도록 배치하면 된다.
• N을 6으로 나눈 나머지가 2이라면, 앞선 홀수 오름차순 리스트에서 1과 3의 위치를 바꾸고 5를 맨 뒤로 보낸다.
  • 즉 (짝수 오름차순), (3, 1, 7, 9, ...., 5) 꼴이 될 것이다.
• N을 6으로 나눈 나머지가 3이라면, 2를 짝수 오름차순 리스트의 맨 끝으로 보내고 1, 3을 홀수 오름차순 리스트의 맨 뒤로 보낸다.
  • 즉 (4, 6, 8, ..., 2), (5, 7, 9, ... , 1, 3) 꼴이 될 것이다.

이런 식으로 모든 N >= 4 에 대한 해 중 하나를 구할 수 있다고 한다. 이건 무슨...?

 

풀이 코드

N = int(input())
ans = sorted(range(1, N+1), key = lambda x : (x % 2, x))
lans, rans = ans[:N//2], ans[N//2:]
if N % 6 == 3 :
  lans.append(lans.pop(0))
  rans.append(rans.pop(0))
  rans.append(rans.pop(0))
  print(*(lans+rans), sep = '\n')
elif N % 6 == 2 :
  rans[0], rans[1] = rans[1], rans[0]
  del rans[2]
  print(*(lans+rans+[5]), sep = '\n')
else :
  print(*ans, sep = '\n')

풀이 실패....