Java) BOJ 9663. N-Queen
문제 링크
제한
- 시간 제한 : 10 초
- 메모리 제한 : 128 MB
문제
-
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
-
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
- 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
👀 풀이
- 어디서 들어본 거 같은데 모르겠어서 구글링했다.
-
참고 블로그 : https://st-lab.tistory.com/118
- 체스판 위에 퀸을 놓은 뒤 그 위치의 다음 위치부터 검사해서 어떤 위치가 퀸이 있는 위치에서 상하좌우 대각선 방향에 있는 곳이라면 그냥 넘어가고 아니라면 퀸을 놓기 위한 함수를 재귀호출하는 것이다.
- 탐색 위치가 체스판의 끝에 도달하면 재귀 호출을 종료한다. (자세한 건 주석에..)
결과
- 시간 : 5320 ms
- 메모리 : 14532 KB