문제 설명
1. N * N 칸의 체스판이 있을 때, 퀸이 서로 공격 못하는 상황을 만들어라(퀸으 개수는 N 개)
풀이
백트랙킹을 사용해서 풀었다.
1. col 이라는 배열은 index 열의 값이 x 번 째 행에 존재한다는 것이다.
2. 속도를 더 빠르게 하려면 대각선과 이전에 작업했던 것 들을 저장하는 배열이 있으면 될 것 이다.
코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.*; | |
| import java.io.*; | |
| /** | |
| * https://www.acmicpc.net/problem/9663 | |
| * BOJ 백준온라인져지 9663 N-Queen 풀이 | |
| */ | |
| public class Main { | |
| private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); | |
| private static int result = 0, N; | |
| private static int col[]; | |
| public static void main(String args[]) throws IOException { | |
| BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
| N = Integer.parseInt(br.readLine()); | |
| col = new int[N + 1]; | |
| // (1, 1) (2, 1) | |
| // (1, 2) (2, 2) | |
| for (int i = 1; i <= N; i++) { | |
| col[1] = i; // 첫 번째 가로 칸의 i 번 째 세로칸을 채운다. (1, i) | |
| dfs(1); | |
| } | |
| bw.write(String.valueOf(result)); | |
| bw.flush(); | |
| } | |
| private static void dfs (int x) { | |
| if (x == N) { | |
| result++; | |
| } else { | |
| for (int i = 1; i <= N; i++) { | |
| int temp = x + 1; | |
| col[temp] = i; | |
| for (int j = 1; j <= x; j++) { | |
| if (col[j] == i || Math.abs(j - temp) == Math.abs(col[j] - i)) { // 대각선, 같은행 확인 | |
| col[temp] = 0; | |
| break; | |
| } | |
| } | |
| if (col[temp] == i) dfs(temp); | |
| } | |
| } | |
| col[x] = 0; | |
| } | |
| } |
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력 1
8
예제 출력 1
92
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 백준온라인져지 1550 16진수 풀이 (0) | 2018.06.21 |
|---|---|
| BOJ 백준온라인져지 11724 연결 요소의 개수 풀이 (0) | 2018.06.21 |
| BOJ 백준온라인져지 1699 제곱수의 합 풀이 (0) | 2018.06.19 |
| BOJ 백준온라인져지 2583 영역 구하기 풀이 (0) | 2018.06.19 |
| BOJ 백준온라인져지 2523 별찍기 - 13 풀이 (0) | 2018.06.18 |