BOJ [3344] N-Queen

2017. 8. 10. 18:31· 알고리즘

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


백트래킹에서 유명한 문제 중 하나인 N-Queen이다.

N값을 입력받고 N * N 크기의 체스판에 N개의 서로 공격하지 못하는 위치에 퀸을 놓는 것.

그런데... 문제가 좀 다르다.

N의 값은 8, 26, 213, 2012, 99991, 99999 중 하나로 정해주었다.

그리고 만족하는 퀸들의 위치를 아무거나 한 개씩만 출력하면 되는 문제이다.

N값 중 99991, 99999이 존재하는 것으로 보아 시간복잡도가 O(n2) 이상이면 시간 초과가 날 것이다.

백트래킹 관련 문제를 별로 풀어본 적도 없어서 공부도 할 겸 백트래킹으로 짜보았으나 역시 시간초과로 실패했다.


번뜩 생각이 난게 같은 x, y축, 대각선의 조건을 거스는 것이 하나 있었다.

나이트는 한 칸 전진 후 대각 방향으로 또 한번을 전진하는데, 각 퀸들이 서로 나이트가 갈 수 있는 경로 상에 있으면 된다.

그렇다면 무언가 규칙이 있다는 셈인데 위키백과가 그 답을 가지고 있었다.


https://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_solutions


Explicit_solutions 탭에 조건과 규칙이 명시되어 있다.

이대로 소스코드를 짜면 끝이다.

#include <cstdio>

int main()
{
	int n;
	bool isOdd = false;
	scanf("%d", &n);

	if (n % 2)	isOdd = true;

	if ((!isOdd && n % 6 != 2) || (isOdd && (n - 1) % 6 != 2))
	{
		if (isOdd)	n--;
		for (int i = 1; i <= n / 2; i++)
			printf("%d\n", 2 * i);
		for (int i = 1; i <= n / 2; i++)
			printf("%d\n", 2 * i - 1);
		if (isOdd)	printf("%d\n", n + 1);
	}

	else if ((!isOdd && n / 6 != 0) || (isOdd && (n - 1) / 6 != 2))
	{
		if (isOdd)	n--;
		for (int i = 1; i <= n / 2; i++)
			printf("%d\n", 1 + (2 * i + n / 2 - 3) % n);
		for (int i = n / 2; i > 0; i--)
			printf("%d\n", n - (2 * i + n / 2 - 3) % n);
		if (isOdd)	printf("%d\n", n + 1);
	}

	return 0;
}


'알고리즘' 카테고리의 다른 글

BOJ [1676] 팩토리얼 0의 갯수  (0) 2017.08.10
BOJ [1874] 스택 수열  (0) 2017.08.10
BOJ [1011] Fly me to the Alpha Centauri  (0) 2017.08.10
BOJ [1463] 1로 만들기  (0) 2017.08.10
BOJ [6588, 9020] 골드바흐의 추측  (0) 2017.08.10
'알고리즘' 카테고리의 다른 글
  • BOJ [1676] 팩토리얼 0의 갯수
  • BOJ [1874] 스택 수열
  • BOJ [1011] Fly me to the Alpha Centauri
  • BOJ [1463] 1로 만들기
감동이중요해
감동이중요해
https://github.com/dhmin5693 dhmin5693@naver.com
감동이중요해
티끌모아 산을 쌓아보자
감동이중요해
전체
오늘
어제
  • 분류 전체보기 (111)
    • 알고리즘 (35)
    • Infra & Dev tools (10)
      • Git (2)
      • Cloud platform (5)
      • Mac, Linux (3)
    • BigData (1)
    • IT 도서 (11)
      • Clean Code (8)
    • Java (36)
      • Spring framework (19)
      • JPA (5)
      • Domain Driven Design (3)
    • Database (2)
      • oracle (1)
      • mysql (0)
    • Computer Science (7)
      • 운영체제 (7)
    • 기타 (9)
      • 크롤링(파이썬) (1)
      • 회고 (4)
      • Career (0)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

  • About me

인기 글

태그

  • 우아한테크캠프2기
  • Java
  • 프로세스
  • AWS
  • JPA
  • 알고리즘
  • Spring
  • Linux
  • 메모리
  • 운영체제
  • Clean Code
  • Database
  • Stream
  • bean
  • Mac
  • 회고
  • 블라인드공채
  • DDD
  • 영속
  • 영속상태

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
감동이중요해
BOJ [3344] N-Queen
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.