어떻게 운 좋게 sds 알고리즘 특강 참여하고 있는데........
1일차 알고리즘 기초 배우면서 풀었던 첫번째 문제.
당일날 못풀어서, 어찌저찌 오늘 풀고 작성한다.
문제 : 백준 9663. N-Queen
N의 입력을 받아서 체스판에 N개의 퀸을 두는데, 서로 공격할 수 없는 위치에 두어야 한다. N개의 퀸을 두는 경우의 수를 구하는 프로그램을 작성해야 한다.
N개의 퀸을 놓을 수 없는 경우라면 불필요한 탐색은 필요하지 않으니, 이러한 조건을 먼저 걸고 탐색을 진행하기 때문에 백트랙킹으로 해결할 수 있다.
문제 해설을 듣기 전에 내가 생각한 풀이는 다음과 같다.
방법 1. n x n 의 배열 모든 곳에 퀸을 두면서 모든 경우의 수를 살피려 했다.
방법 2. n x n 배열을 탐색하면서 해당 행, 열에 있으면 퀸을 못놓는 경우를 이용하여 구현
내가 생각했던 풀이는 1번이고, 2번은 강사님께서 이러한 방법으로 구현하겠죠? 라고 하셨던 방법이다.
두 방법 모두 TLE 난다고 하신다.
아래와 같은 풀이를 알려주셨다.
[n][n]행렬을 생성할 필요도 없이 배열 3개만으로 처리가 가능한다.
대각선 방문 처리가 이해가 안될 수도 있는데, 그림으로 그려서 표현하고 싶지만, 마우스가 현재 없으므로 스킵.
/*
백준 9663. n-queen
*/
package Day1_Algorithm_Basic;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class boj9663 {
static int cnt, n;
static int[] visit_y; // 열의 퀸 유무 체크 배열
static int[] visit_l; // 왼쪽 방향으로 내려가는 대각선 퀸 유무 체크 배열
static int[] visit_r; // 오른쪽 방향으로 내려가는 대각선 퀸 유무 체크 배열
static void back(int x) {
// 행 x의 값이 n인 경우, 즉 체스판 가장 아래까지 퀸이 배치된 경우 경우의 수를 증가시키고 종료
if (x == n) {
cnt++;
return;
}
// x번째 행의 y번째 열을 탐색
for (int y = 0; y < n; y++) {
// 순서대로 열, 대각선 오, 왼 방향의 퀸 유무 확인
if (visit_y[y] == 0 && visit_r[x - y + (n + 1)] == 0 && visit_l[x + y] == 0) {
visit_y[y] = 1;
visit_l[x+y] = 1;
visit_r[x - y + (n + 1)] = 1;
back(x + 1); // 퀸 유무 확인 후, 다음 행 탐색
visit_y[y] = 0;
visit_l[x+y] = 0;
visit_r[x - y + (n + 1)] = 0;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
visit_y = new int[n];
visit_l = new int[2 * n + 1];
visit_r = new int[2 * n + 1];
back(0);
System.out.println(cnt);
}
}