문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
나의 풀이
n퀸의 문제는 기본 알고리즘에 대해 배울때 이미 한 번 익혔던 알고리즘이라 접근법은 기억하고 있는 방법으로 했다. 체스판의 1번째 부터 n번째 행까지 퀸을 놓으면서 이전 행과 퀸이 겹치지 않는지 체크하면서 모든 경우의 수를 놓아보도록 하고 성공할때마다 count를 1씩 증가시켜준다. 이번 풀이는 다른 부분은 직접 작성한 코드인데 다른 사람 풀이중에서 이전 행과 퀸이 겹치지 않는지 파악하는 조건이 좀 신선한 풀이가 있길래 가져다가 적용해보았다.
코드
import java.util.*;
import java.io.*;
public class Main {
public static int count;
public static boolean isPoss(int[] board, int row) {
for(int i=1; i<row; i++) {
if(board[i] == board[row]) //다른 행에 같은 열이 있는 경우.
return false;
if(Math.abs(i-row)==Math.abs(board[i]-board[row])) //대각 선상 있는 경우.
return false;
}
return true;
}
public static void dfs(int[] board, int n, int row) {
if(row==n){ //현재 행이 체스판 마지막 행인 경우 리턴
count++;
return;
}
row++;//다음행 선택
for(int i=1; i<=n; i++) {
board[row] = i; //다음행에 일단 i번째 열에 퀸을 넣어보고 체크한다.
if(isPoss(board, row)) //다음행 i번째 퀸을 놓을 수 있으면 놓고, 그 다음행으로 넘어간다.
dfs(board, n, row);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] board;
count = 0;
for(int i=1; i<=n; i++) {
board = new int[n+1]; // 1~n행 크기의 체스판을 생성한다.
board[1] = i; //체스판의 1번째 줄(행) 중에서 i열 위치에 퀸을 놓고 시작한다.
dfs(board, n, 1);
}
bw.write(count+"\n");
bw.flush();
}
}'Baekjoon-Algorithm > 백트래킹' 카테고리의 다른 글
| 백준 2580 스도쿠 java 풀이 (0) | 2020.08.25 |
|---|