[백준] 9663 N-Queen - 브루트포스(BruteForce) + 시간초과(TimeOut) JAVA

https://www.acmicpc.net/problem/9663

9663번: N-Queen

코드설명

브루트포스(BruteForce) + 시간초과(TimeOut) 문제입니다.

 

처음에는 완전탐색을 통해 진행했습니다만, 이 문제 같은경우 Queen의 위치를 고려해야하기에  조금 더 최적화 시킬 수 있습니다.

 

스택이 너무 쌓여 메모리초과가 나는 주 원인의 코드를 비교해봅시다.

 

먼저 스택이 쌓여 메모리초과가 나는 simulate 재귀함수입니다.

아래 코드를 보듯이, 저는 "모든"경우를 다 확인합니다. 이렇게 진행할경우, 퀸은 한 행에 놓으면 해당 행에는 처리할 수 없는데도, 한 행을 다시 한번 도므로 불필요합니다.

public static void simulate(int level, int r, int c, int cnt) {
    if(cnt == N) {
        answer += 1;
        return ;
    }
    if(c >= N) {
        r = r + 1;
        c = 0;
    }
    if(r >= N) {
        return ;
    }

    //근처에 퀸이 있는지 없는지 검사해야한다.
    if(arr[r][c] == false && checkQueen(r, c) == true) {
        arr[r][c] = true;
        simulate(level + 1, r, c + 1, cnt + 1);
        arr[r][c] = false;
    }
    simulate(level + 1, r, c + 1, cnt);

}

 

 

퀸의 움직임을 최적화한 코드입니다.

또한 문제를 읽어보면, NXN 개의 Map에서 퀸의 조건을 마주치면서 N개를 넣으려면 반드시 각 행마다 모든 Queen이 들어가야합니다. 그러므로 r==N 까지 도달한다면 N개를 모두 삽입한 것 입니다. 이러한 코드는 성공할경우 바로 r을 이동시키므로 문제가 없습니다.

public static void simulate(int r) {
    if(r == N) {
        answer++;
        return ;
    }

    for(int c = 0; c < N;c++) {
        if(checkQueen(r, c) == true) {
            arr[r][c] = true;
            simulate(r + 1);
            arr[r][c] = false;
        }
    }
}

 

또한 위의 재귀함수를 수정하는것 외에도 Queen의 위치를 확인하는 코드 또한 수정이 필요합니다.

 

먼저 시간초과를 유발하는 코드입니다.

public static boolean checkQueen(int r, int c) {
    //북쪽에서부터 시계방향으로.
    int[] dx = {-1, -1,-1};
    int[] dy = {-1, 0, 1};

    //3방향을 모두 확인합니다.
    for(int dir = 0; dir < 3; dir++) {
        int startR = r;
        int startC = c;
        while(true) {
            startR += dx[dir];
            startC += dy[dir];
            if(startR < 0 || startR >= N || startC < 0 || startC >= N) break; 
            if(arr[startR][startC] == true) {
                return false;
            }
        }
    }

    return true;
}

각 방향을 총 3번씩 모두 확인합니다.

 

하나의 반복문에서 3가지 방향을 모두 확인합니다.

public static boolean checkQueen(int r, int c) {
    // 북쪽, 북서쪽, 북동쪽 방향으로 퀸이 있는지 확인합니다.
    for(int i = 0; i < r; i++) {
        if(arr[i][c]) return false; // 같은 열에 퀸이 있는지 확인
        if(c - (r - i) >= 0 && arr[i][c - (r - i)]) return false; // 북서쪽 대각선에 퀸이 있는지 확인
        if(c + (r - i) < N && arr[i][c + (r - i)]) return false; // 북동쪽 대각선에 퀸이 있는지 확인
    }
    return true;
}

 

코드

시간초과 해결코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {

	public static int N,M, K;
	public static boolean[][] arr;
	public static int answer =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());
    	arr = new boolean[N][N];

    	simulate(0);
    	System.out.println(answer);
    }

    
    public static void simulate(int r) {
    	if(r == N) {
    		answer++;
    		return ;
    	}
    	
    	for(int c = 0; c < N;c++) {
    		if(checkQueen(r, c) == true) {
    			arr[r][c] = true;
    			simulate(r + 1);
    			arr[r][c] = false;
    		}
    	}
    }
    public static boolean checkQueen(int r, int c) {
        // 북쪽, 북서쪽, 북동쪽 방향으로 퀸이 있는지 확인합니다.
        for(int i = 0; i < r; i++) {
            if(arr[i][c]) return false; // 같은 행에 퀸이 있는지 확인
            if(c - (r - i) >= 0 && arr[i][c - (r - i)]) return false; // 북서쪽 대각선에 퀸이 있는지 확인
            if(c + (r - i) < N && arr[i][c + (r - i)]) return false; // 북동쪽 대각선에 퀸이 있는지 확인
        }
        return true;
    }
    
}

브루트포스로 풀경우 시간초과 및 메모리초과가 나옵니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {

	public static int N,M, K;
	public static boolean[][] arr;
	public static int answer =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());
    	arr = new boolean[N][N];

    	simulate(0, 0, 0, 0);
    	System.out.println(answer);
    }

	//퀸은 상하좌우, 대각선까지 고려해야한다.
    public static void simulate(int level, int r, int c, int cnt) {
    	if(cnt == N) {
    		answer += 1;
    		return ;
    	}
    	if(c >= N) {
    		r = r + 1;
    		c = 0;
    	}
    	if(r >= N) {
    		return ;
    	}
    	
    	//근처에 퀸이 있는지 없는지 검사해야한다.
    	if(arr[r][c] == false && checkQueen(r, c) == true) {
    		arr[r][c] = true;
    		simulate(level + 1, r, c + 1, cnt + 1);
    		arr[r][c] = false;
    	}
    	simulate(level + 1, r, c + 1, cnt);
    	
    }
    
    public static boolean checkQueen(int r, int c) {
    	//북쪽에서부터 시계방향으로.
    	int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    	int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

    	//8방향을 모두 확인합니다.
    	for(int dir = 0; dir < 8; dir++) {
    		int startR = r;
    		int startC = c;
    		while(true) {
    			startR += dx[dir];
    			startC += dy[dir];
    			if(startR < 0 || startR >= N || startC < 0 || startC >= N) break; 
    			if(arr[startR][startC] == true) {
    				return false;
    			}
    		}
    	}
    	
    	return true;
    }
    
}

 

 

다른 코드를 참고해보았습니다. 가장 효율적인 속도의 코드입니다.

package Main;

import java.io.IOException;
import java.util.Scanner;


public class Main {
	
	//같은열 기준 y를 기준
	static boolean isused1[] = new boolean[40];
	//우측상단대각선기준 x+y ==
	static boolean isused2[] = new boolean[40];
	//우측하단대각선기준 x-y 인데 음수를 피하기위해 x-y+N-1 로 진행
	static boolean isused3[] = new boolean[40];
	static int N,cnt=0;
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		
		func(0);
		System.out.println(cnt);
	}
	
	public static void func(int cur) {
		if(cur == N) {
			cnt ++;
			return ;
		}
		
		
		//cur이 x임, i가 y임
		//이유는 한행씩 채워가면서 진행하기에 cur : 0 은 0번째 행을 채우자는 의미임
		for(int i=0;i<N;i++) {
			if(isused1[i] || isused2[cur+i] || isused3[cur-i+N-1]) {
				continue;
			}
			isused1[i] = true;
			isused2[cur+i] = true;
			isused3[cur-i+N-1] = true;
			func(cur+1);
			isused1[i] = false;
			isused2[cur+i] = false;
			isused3[cur-i+N-1] = false;
			
		}
	}


	
}