브루트포스 문제는 풀이방식이 다양해서 더 어려운 것 같다. 익숙해지기 위해 브루트포스 문제 리뷰를 많이 하려고 한다.
이번에 풀어본 문제는 N-Queen 문제인데, 여러번의 3번의 시도끝에 성공한 문제라, 내가 잘못했던 부분이 무엇이었는지를 기록하고자 내 시도를 정리하려고 한다.
첫번째 시도
- 격자의 (0,0) 부터 시작하여 (N,N) 까지 조회
- 공격받지 않을 수 있는 위치가 있으면 Queen을 두고 재귀
- 놓은 Queen의 수가 N개를 모두 충족했을 시, count를 추가하고 또 다음 놓을 수 있는 N번째를 찾아 계속해서 count를 추가.
- 더이상 놓을 수 있는 N번째 Queen이 없을 시, 재귀스택을 벗어나 다음 N-1번째 queen의 위치를 변경한 후 다시 재귀.
- 재귀 반복
package prob16;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class DayProb16 {
private static int N;
private static boolean[][] queens;
public static void main(String[] argv) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int count = 0;
for (int i = 0; i < N*N; i++){
queens = new boolean[N][N];
count += bf(i, 1);
}
System.out.println(count);
}
public static int bf(int start, int cnt){
attackable(start/N, start%N);
int incount = 0;
for (int i = start+1; i < N*N; i++){
if(queens[i/N][i%N]){continue;}
if (cnt + 1 >= N) {
incount++;
continue;
}
incount += bf(i, cnt + 1);
}
return incount;
}
public static void attackable(int row, int col){
// 가로,세로 열 모두 공격가능
for (int i = 0; i < N; i++){
queens[row][i] = true;
queens[i][col] = true;
}
for (int i = -N; i < N; i++){
if (row+i >= 0 && row+i < N && col+i >=0 && col+i < N) {
queens[row+i][col+i] = true;
}
if (row+i >= 0 && row+i < N && col-i < N && col-i >= 0) {
queens[row+i][col-i] = true;
}
}
}
}결과 : 틀렸습니다
=> 재귀마다 queens 배열을 원상복구 시켜줘야 하는데 그렇지 않았다. 재귀 후 배치했던 queen은, 재귀에서 나온 후 다시 제거한 후 설정한 attackable 영역을 다시 원상복구 해야한다.
- 방법1) queens 를 매 재귀마다 복사해서 넘기거나 (매 재귀마다 O(N^2)의 시간복잡도)
- 방법2) 재귀 나오기 직전에 attackable() 이 변경한 좌표를 모두 원상복귀 ⇒ 매우 복잡, 좌표 저장을 위한 추가 공간 필요.
두번째 시도
attackable() 이 변경했던 좌표를 저장한 후, 재귀에서 나올 때 해당 좌표들을 다시 원상복구 시키는 방법이다.
하지만, 원상복구좌표를 위한 추가 메모리 공간이 "매 재귀마다" 필요하다.
package prob16;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class DayProb16 {
private static int N;
private static boolean[][] queens;
public static void main(String[] argv) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int count = 0;
for (int i = 0; i < N*N; i++){
queens = new boolean[N][N];
count += bf(i, 1);
}
System.out.println(count);
}
public static int bf(int start, int cnt){
List<int[]> changed = attackable(start/N, start%N);
int incount = 0;
// 다음열부터
for (int i = (start/N+1)*N; i < N*N; i++){
if(queens[i/N][i%N]){continue;}
if (cnt + 1 >= N) {
incount++;
continue;
}
incount += bf(i, cnt + 1);
}
for (int[] pair : changed){
queens[pair[0]][pair[1]] = false;
}
return incount;
}
public static List<int[]> attackable(int row, int col){
List<int[]> changed = new ArrayList<>();
// 가로,세로 열 모두 공격가능
for (int i = 0; i < N; i++){
if (!queens[row][i]) {
changed.add(new int[]{row, i});
queens[row][i] = true;
}
if(!queens[i][col]){
changed.add(new int[]{i, col});
queens[i][col] = true;
}
}
for (int i = -N; i < N; i++){
if (row+i >= 0 && row+i < N && col+i >=0 && col+i < N) {
if(!queens[row+i][col+i]) {
changed.add(new int[]{row+i, col+i});
queens[row+i][col+i] = true;
}
}
if (row+i >= 0 && row+i < N && col-i < N && col-i >= 0) {
if(!queens[row+i][col-i]) {
changed.add(new int[]{row+i, col-i});
queens[row+i][col-i] = true;
}
}
}
return changed;
}
}결과 : 메모리 초과
- 로컬에서 돌렸을 때 테스트케이스는 모두 정상적으로 통과하나, 역시 메모리 초과가 뜬다.
- 재귀가 존재하는데, 매 재귀마다 attackable()이 새로운 ArrayList를 생성하기 때문이다.
마지막 시도
우선, 복잡했던 재귀식에서 end case 를 명확히 한 후 (row의 범위가 N을 벗어날 때 까지) backtracking 형식으로 변경했다.
public static int dfs(int depth){
if (depth >= N) {return 1;}
...그리고, attackable 영역인지를 더 쉽게 확인하기 위해 2차원 배열을 선언한 것이 아니라, 같은 column 상, 같은 \ 대각선상, 같은 / 대각선상을 의미하는 배열을 정의했다.
private static boolean[] col;
private static boolean[] diag1; // "/"
private static boolean[] diag2; // "\"
int N = Integer.parseInt(br.readLine());
col = new boolean[N];
diag1 = new boolean[2*N-1];
diag2 = new boolean[2*N-1]; 이렇게하면 attackable 영역인지 확인하는 로직과, 영역을 설정하는 로직과, 원상복구 로직이 훨씬 더 간편하다.
그리고, 매 row 마다 1~9 까지의 col을 확인하며, 각 row에서 Queen을 둘 수 있는 column과 대각선상을 확인하며 재귀한다.
int incount = 0;
for (int i = 0; i < N; i++){
int d1 = depth + i;
int d2 = depth - i + (N - 1);
if (col[i] || diag1[d1] || diag2[d2]) {continue;}
col[i] = true;
diag1[d1] = true;
diag2[d2] = true;
incount += dfs(depth+1);
col[i] = false;
diag1[d1] = false;
diag2[d2] = false;
}
return incount;전체코드
package prob16;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class DayProb16 {
private static int N;
private static boolean[] col;
private static boolean[] diag1; // "/"
private static boolean[] diag2; // "\"
public static void main(String[] argv) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
col = new boolean[N];
diag1 = new boolean[2*N-1];
diag2 = new boolean[2*N-1];
System.out.println(dfs(0));
}
public static int dfs(int depth){
if (depth >= N) {return 1;}
int incount = 0;
for (int i = 0; i < N; i++){
int d1 = depth + i;
int d2 = depth - i + (N - 1);
if (col[i] || diag1[d1] || diag2[d2]) {continue;}
col[i] = true;
diag1[d1] = true;
diag2[d2] = true;
incount += dfs(depth+1);
col[i] = false;
diag1[d1] = false;
diag2[d2] = false;
}
return incount;
}
}결과
드디어 성공했다!
스터디원의 풀이
인상깊었던 스터디원의 풀이가 있어 공유하려고 한다. 코드도 훨씬 간단하고 직관적이다. 나는 왜저렇게 어렵게 생각하고 풀려 했는지 현타가 올 정도이다.
class Solution {
int[] board;
int count = 0;
int answer = 0;
public int solution(int n) {
board = new int[n];
backtracking(0, n);
return answer;
}
// 같은 idx 이거나 대각선이면
private void backtracking(int start, int n){
// n개 배치 완료 시 종료
if(start == n){
answer++;
return;
}
// 이번 행에 넣을 숫자를 0~n-1 반복
for(int i=0; i<n; i++){
// 이전과 비교해서 이번에 놓을 게 안전하면 백트래킹
if(isSafe(start, i)){
board[start] = i;
backtracking(start+1, n);
}
}
}
private boolean isSafe(int now, int num){
for(int prev=0; prev<now; prev++){
// 같은 행이거나 대각선
if(board[prev] == num || Math.abs(board[prev] - num) == Math.abs(prev - now)){
return false;
}
}
return true;
}
}- 백트래킹 로직은 나와 같으며, 매 row에서 1~9 col까지 확인하며, 이전 배치Queen들과 attackable한지 아닌지를 확인하는 이 로직만 다르다.
- attackable 인지 확인하기 위한 배열을
int[] board = new int[n];하나만 선언한다.
이 배열은 지금까지의 row에서 선택한 col의 인덱스를 의미한다. - 이 배열을 사용해서 이전까지 배치했던 queen들을 순회하며 같은 행이거나 같은 대각선인지를 확인한다.
- 같은 대각선인지 확인하기 위해서 사용한 이 방법이 아주 천재적이다.
x방향 차이와 y방향 차이가 같으면 같은 대각선인 것이다.
Math.abs(board[prev] - num) == Math.abs(prev - now)
🫵 안녕하세요, 백엔드 공부하는 초보개발자 홍대의 입니다!