9663번 N-Queen

문제

• 백준 9663번 N-Queen 
• 골드 4
• 백트래킹 유형
• https://www.acmicpc.net/problem/9663

---

 

문제 풀이

 

1.  메모리 초과

• 이미 n * n 크기의 2차원 배열로 메모리가 거의 꽉 차서 flag를 위한 배열을 사용하니 메모리가 초과한 것 같다. 

public class Main {
	public static int count = 0;
	public static int n;
	public static int arr[][];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        arr = new int[n][n];
        dfs(0);
        System.out.println(count);
    }
    public static void dfs (int dep) {
    	if (dep == n) {
    		count++;
    		return;
    	}
    	for (int i=0; i < n; i++) {
    		if (arr[dep][i] == 0) {
    			check(dep, i);
    			dfs(dep + 1);
    			uncheck(dep, i);
    		}
    	}	
    }
    public static void check(int y, int x) {
        int[] xFlag = {-1, -1, 1, 1}; 
        int[] yFlag = {-1, 1, -1, 1};
        
        for (int i = 0; i < n; i++) {
            arr[y][i]++; 
            arr[i][x]++; 
        }

        for (int i = 0; i < 4; i++) { 
            int newX = x;
            int newY = y;
            while (true) {
                newX += xFlag[i]; 
                newY += yFlag[i];
                if (newX < 0 || newX >= n || newY < 0 || newY >= n) {
                    break; 
                }
                arr[newY][newX]++; 
            }
        } 
    }
    
    public static void uncheck(int y, int x) {
        int[] xFlag = {-1, -1, 1, 1};
        int[] yFlag = {-1, 1, -1, 1};


        for (int i = 0; i < n; i++) {
            arr[y][i]--;
            arr[i][x]--;
        }

        for (int i = 0; i < 4; i++) { 
            int newX = x;
            int newY = y;
            while (true) {
                newX += xFlag[i]; 
                newY += yFlag[i];
                if (newX < 0 || newX >= n || newY < 0 || newY >= n) {
                    break; 
                }
                arr[newY][newX]--; 
            }
        }  
    }
}

 

 

2. 성공

• 배열을 없애고 0부터 n까지 for문을 이용해서 대각선을 처리했다.

public class Main {
	public static int count = 0;
	public static int n;
	public static int arr[][];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        arr = new int[n][n];
        dfs(0);
        System.out.println(count);
    }
    public static void dfs (int dep) {
    	if(dep == n) {
    		count++;
    		return;
    	}
    	for(int i=0; i < n; i++) {
    		if(arr[dep][i]==0) {
    			check(dep,i);
    			dfs(dep + 1);
    			uncheck(dep,i);
    		}
    		
    	}
    	
    }
    public static void check(int y, int x) {
        for (int i = 0; i < n; i++) {
            arr[y][i]++;
            arr[i][x]++;
        }
        for (int i = 1; i < n; i++) {
            if (y + i < n && x + i < n) arr[y + i][x + i]++;
            if (y + i < n && x - i >= 0) arr[y + i][x - i]++;
            if (y - i >= 0 && x + i < n) arr[y - i][x + i]++;
            if (y - i >= 0 && x - i >= 0) arr[y - i][x - i]++;
        }
        arr[y][x]--;
    }
    
    public static void uncheck(int y, int x) {
        for (int i = 0; i < n; i++) {
            arr[y][i]--;
            arr[i][x]--;
        }
        for (int i = 1; i < n; i++) {
            if (y + i < n && x + i < n) arr[y + i][x + i]--;
            if (y + i < n && x - i >= 0) arr[y + i][x - i]--;
            if (y - i >= 0 && x + i < n) arr[y - i][x + i]--;
            if (y - i >= 0 && x - i >= 0) arr[y - i][x - i]--;
        }
        arr[y][x]++; 
    }
}

 

 

3. 다른곳에서 본 코드 

• 메모리적으로 매우 뛰어난 코드 겸 대각선을 처리한 방식이 굉장히 신기했다.

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int []arr;
	public static int n;
	public static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		n = Integer.parseInt(bf.readLine());
		arr = new int[n];
		dfs(0);
		System.out.println(count);
	}
	public static void dfs(int dep) {
		if(dep==n) {
			count++;
			return;
		}
		for(int i=0;i<n;i++) {
			arr[dep] = i;
			if(possible(dep)) {
				dfs(dep+1);
			}
		}
	}
	public static boolean possible(int col) {
		for(int i = 0 ; i < col ; i++) {
			//행에 일치하는게 있는지 판별
			if(arr[i]==arr[col]) {
				return false;
			}
			//대각선에 일치하는게 있는지 판별
			else if(Math.abs(col-i) == Math.abs(arr[col]-arr[i])) {
				return false;
			}
				
			}
			
			return true;
	}

}