[BOJ] 백준 3344번 N-Queen (백트래킹x) (JAVA)

#3344 N-Queen

난이도 : 플래티넘 5

유형 : Case work

3344번: N-Queen

▸ 문제

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 백트래킹 문제를 풀고 그 문제의 업그레이드 버전이라 생각하고 들어왔는데 전혀 다른 유형의 문제였다. 케이스 추론 문제로 컴퓨팅 사고와는 거리가 먼 문제이다.

 

 

풀이는 해당 링크를 참고하였다.

 

이러한 식을 도출해내는 과정이 어려워 플래티넘5인 것 같다. 공식만 알면 구현해내는데에는 전혀 문제가 없다.

1. If the remainder from dividing n by 6 is not 2 or 3 then the list is simply all even numbers followed by all odd numbers not greater than n.

2. Otherwise, write separate lists of even and odd numbers (2, 4, 6, 8 – 1, 3, 5, 7).

3. If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end (3, 1, 7, 5).

4. If the remainder is 3, move 2 to the end of even list and 1,3 to the end of odd list (4, 6, 8, 2 – 5, 7, 1, 3).

5. Append odd list to the even list and place queens in the rows given by these numbers, from left to right (a2, b4, c6, d8, e3, f1, g7, h5).

 

위의 규칙을 정리하자면 다음과 같다.

1. N이 2또는 3으로 나누어지는 않는다면 간단한게 n이하의 홀수 -> 짝수로 구성된다. (ex. 5 -> 1,3,5,2,4)
2. 1에 해당하지 않으면 짝수와 홀수는 다음과 같이 나누어진다 (2, 4, 6, 8, 1, 3, 5, 7)
   1. N이 만약 2로 나누어진다면 1과 3의 자리를 바꾸고 5를 홀수의 가장 마지막으로 옮긴다  (3, 1, 7, 5)
   2. N이 만약 3로 나누어진다면 2를 짝수의 가장 마지막으로 옮기고 1,3을 홀수의 가장 마지막으로 옮긴다. (4, 6, 8, 2, 5, 7, 1, 3)

 

 

🐶 실행결과 예제

• 8 queens (remainder 2): 2, 4, 6, 8, 1, 3, 5, 7
• 14 queens (remainder 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
• 15 queens (remainder 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
• 20 queens (remainder 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.

*백준 예제 출력에는 N=8 출력이 다르게 나와있는데 무시하고 해당 규칙대로 출력하면 된다.

 

 

 

구현 코드  

import java.io.*;

public class Main {

 	public static void main(String[] args) throws IOException{
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int n = Integer.parseInt(br.readLine());
 		
 		if(n%6 !=2 && n%6 !=3) {
 			for(int i=1; i<=n/2; i++) {
 				sb.append(2*i-1).append("\n");
 			}
 			if(n%2 ==1) {
 				sb.append(n).append("\n");
 			}
 			for(int i=1; i<=n/2; i++) {
 				sb.append(2*i).append("\n");
 			}
 			
 		}else if(n % 6 == 2) {
 			
 			for(int i=1; i<=n/2; i++) {
 				sb.append(2*i).append("\n");
 			}
 			sb.append(3).append("\n");
 			sb.append(1).append("\n");
 			for(int i=n/2+2; i<n-1; i++) {
 				sb.append(2*(i-n/2 +1)+1).append("\n"); // 2x+1 
 			}
 			sb.append(5).append("\n");
 			
 		}else if(n%6 ==3) {
 			for(int i=2; i<=n/2; i++) {
 				sb.append(2*i).append("\n");
 			}
 			sb.append(2).append("\n");
 			
 			for(int i=n/2; i<n-2; i++) {
 				sb.append((i-n/2 +2)*2+1).append("\n");
 			}
 			sb.append(1).append("\n");
 			sb.append(3).append("\n");
 		}
 		
 		System.out.println(sb.toString());
	}
}