문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
풀이
import java.io.*;
public class Main {
static int[] dx = {-1, -1};
static int[] dy = {-1, 1};
static BufferedReader br;
static int n, ans;
static boolean[][] board;
public static void main(String[] args) throws IOException {
init();
for (int i = 0; i < n; i++) {
dfs(0, i);
}
System.out.println(ans);
}
static void init() throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
board = new boolean[n][n];
}
static void dfs(int x, int y) {
//목적지인가? : n개까지 말을 놓았을 때
if(x == n-1) {
ans++;
return;
}
//퀸 놓기
board[x][y] = true;
//연결된 곳 순회 : x행의 열
for (int i = 0; i < n; i++) {
//갈 수 있는가? : 서로 공격할 수 없는 위치
if(check(x+1, i)) {
dfs(x+1, i);
}
}
//말 빼기
board[x][y] = false;
}
static boolean check(int x, int y) {
//세로 줄에 퀸이 있는지 확인
for (int i = 0; i < n; i++) {
if(board[i][y]) {
return false;
}
}
//왼쪽 위, 오른쪽 위 대각선만 알면 된다. (현재 줄에서 놓을 수 있는지만 보면 되기 때문에)
int xx, yy;
for (int i = 0; i < 2; i++) {
xx = dx[i] + x;
yy = dy[i] + y;
while(xx >= 0 && yy >= 0 && xx < n && yy < n) {
if(board[xx][yy]) {
return false;
}
xx += dx[i];
yy += dy[i];
}
}
return true;
}
}
백트래킹의 대표격인 문제이다. dfs로 백트래킹의 개념을 배우기 좋다.
n+n의 체스판에 n개의 퀸이 서로 죽일 수 없게 놓으려면 결국 각 줄 마다 한개씩은 놓아져 있어야 한다.
이 점을 활용해서 0,0부터 말을 놓고 다음 줄에서 갈 수 있는 위치로 dfs해서 쭉 가다가 더 이상 놓을 곳이 없다면 자연스레 빠져나오게 된다. 만약 n개의 말이 놓아졌다는 것은 모든 n개의 말이 서로 공격할 수 없게 놓았다는 뜻이므로 답 + 1 해주고 다시 빠져나오면 된다.
'Dev > PS' 카테고리의 다른 글
[백준] 1753 최단경로 java (0) | 2022.08.05 |
---|---|
[백준] 2252 줄 세우기 java (0) | 2022.07.26 |
[백준] 1103 게임 java (0) | 2022.07.23 |
[백준] 9202 Boggle java (0) | 2022.07.22 |
[백준] 1339 단어 수학 java (0) | 2022.07.21 |