백준 9663번: N-Queen에서 최적화 방안 고민..! (JAVA/자바)
- 문제 소개
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
해당 문제는 백트래킹을 이용해 풀 수 있는 문제 중 하나이다.
해당 답안은 n = 4일때, 나올 수 있는 답안 중 하나이다.
- 해결책 최적화에 대한 고민
이 문제는 너무나 유명한 백트래킹 문제라 바로 백트래킹을 적용해보았다.
public class baek9663 {
static int N;
static long total = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int[] visited = new int[N];
func(0, visited);
System.out.print(total);
}
public static void func(int cdx, int[] visited) {
if (cdx == N) {
total++;
return;
}
for (int i = 0; i < N; i++) {
visited[cdx] = i;
if(checked(cdx, visited))
func(cdx + 1, visited);
}
}
public static boolean checked(int cdx, int[] visited) {
for (int i = 0; i < cdx; i++) {
if (visited[cdx] == visited[i] || cdx - i == Math.abs(visited[cdx] - visited[i]))
return false;
}
return true;
}
}
내가 짠 코드의 핵심은 checked 함수이다. 해당 함수를 통해, 각각의 조건을 통해 cdx와 i가 같은 열에 있는지, 그리고 같은 대각선에 위치하는지 확인하는 함수이다. 작동도 아주 깔끔히 굴러가지만, 마음에 걸리는 부분이 있었다. 바로 다른 분들과 수행시간을 비교했을 때, 내 수행시간은 그리 빠른 편이 아닌 것이다..!
한동안 이 문제를 어떻게 효율적으로 해결하면 좋을지 고민하다 시간이 흘렀다... 그러던 중에, 인하대 도서관에서 책을 빌리다 우연하게 알고리즘 트레이닝 (2판)이란 책을 보게 되었다!
우연하게 읽은 책에서 최적화의 실마리를 찾을 수 있었다! 바로 배열 3개를 이용하는 방법이다!
col, diag1, diag2 라는 boolean 타입의 1차원 배열 3개를 사용한다. 1차원 배열의 크기는 각각 N, 2*N, 2*N으로 지정한다.
col -> 해당 열을 사용했는 지를 묻는 1차원 배열
diag1, diag2 -> 왼쪽 아래로 가는 대각선, 오른쪽 아래로 가는 대각선에 겹치는 것이 있는지 추적용 1차원 배열
왜 diag1과 diag2의 크기가 2*N인지 말해보자면 다음과 같다. N = 4일때, 즉 4*4 보드판 위에서 오른쪽 아래 대각선과 왼쪽 아래 대각선을 그려보면 각각 7개씩 나오는 것을 알 수 있다.즉 2*N - 1 개의 대각선이 필요한데, 혹시 모를 OutOfIndex를 피하기 위해 2*N으로 지정하였다.
실제 보드판을 가지고 각각 배열에 맞게 인덱싱을 해보았다. 위 그림을 통해 어떤 구조로 인덱싱을 하는지 도움을 줄려 제작하였다!
다음은 해당 아이디어를 적용한 코드이다.
public class baek9663Better {
static int N;
static long total = 0;
static boolean[] col;
static boolean[] diag1;
static boolean[] diag2;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
col = new boolean[N];
diag1 = new boolean[2* N];
diag2 = new boolean[2* N];
func(0);
System.out.print(total);
}
public static void func(int y) {
if (y == N) {
total++;
return;
}
for (int x = 0; x < N; x++) {
if (isNotSafe(x, y)) continue;
col[x] = diag1[x + y] = diag2[x - y + (N - 1)] = true;
func(y + 1);
col[x] = diag1[x + y] = diag2[x - y + (N - 1)] = false;
}
}
public static boolean isNotSafe(int x, int y) {
return col[x] || diag1[x + y] || diag2[x - y + (N- 1)];
}
}
아까의 코드와 차이점은, checked 대신 isNotSafe라는 함수가 사용된 점이다. checked와 다르게 isNotSafe는 한번의 조회로 결과를 바로 출력할 수 있다. 기본적으로 백트래킹 알고리즘은 같으나, 조회에서 checked는 O(N)의 시간 복잡도를 isNotSafe는 O(1)의 시간 복잡도를 나타낸다. 조회 함수를 호출을 많이 하면 할 수록 두 알고리즘의 시간 차이는 더 벌어지는 것이다!
실제 수행시간도, 시간 복잡도의 차이에 의해 훨씬 줄어든 것을 알 수 있다. Space를 좋은 방향으로 Time과 트레이드 오프하였기에 개인적으로 이 접근법이 더 효율적이라 생각한다!