[BJ 3344] N-Queens

대연.

·

2021. 2. 24. 20:00

서론

 

 

3344번: N-Queen

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

www.acmicpc.net

N-Queens의 매운 맛 문제가 있길래 시도해봤는데 시간초과로 박살이 났다. 인풋으로 99999가 들어가는데 시간 초과가 나는건 자명했는데 아무 생각없이 정답률을 까먹었다. 대체 어떻게 푸는건가 싶어서 구글링해봤는데, 이 문제에만 특별히 적용되는 알고리즘이 있었다. 태그에 백트래킹이 붙어있지 않을 때 알아봤었어야 했는데...

 

 

Eight queens puzzle - Wikipedia

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an exampl

en.wikipedia.org

근데 영어 위키인데 아무도 번역본을 올려놓지 않아서 열뻗쳐서 쓰는 포스트다.

Existence of solutions 절을 참고하면 된다.

 

  1. 만약 N을 6으로 나누었을 때, 나머지가 2나 3이 아니라면 정답의 리스트는 n보다 작은 홀수들의 리스트를 만들고, 리스트의 크기가 N이 될 때까지 2부터 4,6,8... 등 짝수를 리스트에 넣는다.
  2. 나머지가 2와 3이라면 짝수 리스트 뒤에 홀수 리스트를 합친다. (ex. N=8일 때 [2,4,6,8,1,3,5,7])
  3. 나머지가 2라면, 1과 3의 위치를 바꾸고 5를 홀수 리스트 맨 뒤로 보낸다. (ex. N=10일 때 홀수 리스트 [1,3,5,7,9]->[3,1,7,9,5]
  4. 나머지가 3이라면, 2를 짝수리스트 맨 뒤로 보내고, 1,3을 짝수리스트 맨 뒤로 보낸다. (ex. N=8일 때 [4,6,8,2] + [5,7,1,3])
  5. 리스트를 그대로 출력하면 정답이 된다.

아래는 몇 가지 예제들이다. 설명이 불충분하다면 예제를 보고 이해하자.

  • N = 14 (나머지 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
  • N = 15 (나머지 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
  • N = 20 (나머지 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.

 

[N-Queens 문제]

문제

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중 하나이다.

코드

최적화 할 여지가 굉장히 많지만 큰 의미가 없는 문제라 실행시간에 의미를 두지 않기로 했다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		int[] sol = new int[N];
		if(N % 6 != 2 && N % 6 != 3) {
//			System.out.println("1");
			int i = 0;
			for(i = 0; i < N; i++) {
				if(2*i+1 > N) break;
				sol[i] = 2*i+1;
			}
			for(int k = i; k < N; k++) {
				sol[k] = 2*(k-i+1);
			}
		}
		else if(N % 6 == 2) {
//			System.out.println("2");
			for(int i = 0; i < N/2; i++) {
				sol[i] = (i+1)*2;
			}
			sol[N/2] = 3;
			sol[N/2+1] = 1;
			int i = 0;
			for(i = N/2+2; i < N-1; i++) {
				sol[i] = 2*(i-N/2+1)+1;
			}
//			sol[N-1] = sol[N-2];
			sol[N-1] = 5;
		}else {
			for(int i = 0; i < N/2-1; i++) {
				sol[i] = (i+2)*2;
			}
			sol[N/2-1] = 2;
			for(int i = N/2; i < N-2; i++) {
				sol[i] = (i-N/2+2)*2+1;
			}
			sol[N-2]=1;
			sol[N-1]=3;
		}
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < N; i++) {
			sb.append(sol[i]+"\n");
		}
		bw.write(sb.toString());
		bw.flush();
//		comb(0);
	}
}

문제의 의의?

없다. 큰 도움이 되지 않는 문제다. 내가 풀이를 고안해내지 못해도 죄책감이 들지 않는 문제다. 도대체 이 알고리즘을 누가 앉은 자리에서 생각해낸단 말인가? 이 알고리즘을 모르는 개발자 100명을 가둬놓고 풀이를 시키면 누가 풀 수 있을까? 아이디어는 다이아몬드급 구현은 브론즈급 문제인데 왜 플래티넘5가 붙었는지 모르겠다. solved.ac 티어 한 끼 식사로 충분하다. 개인의 발전에는 도움이 되지 않으니 이 문제를 못 풀었다고 좌절하지 말자.

'프로그래밍 > Algorithm' 카테고리의 다른 글

[BOJ 1092] 배  (0) 2021.03.04
[BOJ 17839] Baba is Rabbit  (0) 2021.03.04
[BJ 3344] N-Queens  (0) 2021.02.24
[BJ 18768] 팀 배정  (0) 2021.02.23
[BOJ 1256] 사전 (풀이 미완성, DP사용 X)  (0) 2021.02.10
[BOJ 3078] 좋은 친구  (0) 2021.02.04

0개의 댓글