Programmers - N-Queen with JAVA

 

 

 

 

로직

- 우선, 완전탐색은 시간복잡도상 불가능하다.

- 퀸이 만약 y=0을 방문한다면 다른 퀸들은 y=0을 더이상 방문하지 못한다.

- 따라서, 다음 퀸은 map[0~11][y+1] 칸 중 하나를 방문가능하다.

 

1. map 생성

2. 탐색 함수로 전달받은 y줄에서 방문하지 않은 x칸 즉, map[x][y] 칸 선택

3. 가로, 대각선 방문 처리 후 y+1과 방문처리한 새로운 맵 전달

-> 더이상 방문할 수 있는 map[0~11][y+1] 이 없다면 return

-> y가 n까지 증가했다면 answer += 1 후 return

 

 

코드

import java.util.*;
class Solution {
    public static int answer = 0;
    public int solution(int n) {
        boolean[][] map = new boolean[n][n];
        find(0, n, map);
        return answer;
    }
    public static void find(int y, int n, boolean[][] map){
        if(y == n){
            answer += 1;
            return;
        }
        for(int x=0; x<n; x++){
            if(map[x][y]){
                continue;
            }
            boolean[][] new_map = visit(map, x, y, n);
            find(y+1, n, new_map);
        }
    }
    public static boolean[][] visit(boolean[][] map, int x, int y, int n){
        boolean[][] result = new boolean[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                result[i][j] = map[i][j];
            }
        }
        for(int i=y; i<n; i++){
            result[x][i] = true;
        }
        int index = 1;
        while(true){
            if(x+index >= n | y+index >= n){
                break;
            }
            result[x+index][y+index] = true;
            index += 1;
        }
        index = 1;
        while(true){
            if(x-index < 0 | y+index >= n){
                break;
            }
            result[x-index][y+index] = true;
            index += 1;
        }
        return result;
    }
}

 

 

import java.util.*;
class Solution {
    public static int answer = 0;
    public int solution(int n) {
        boolean[][] map = new boolean[n][n];
        find(n, 0, map);
        return answer;
    }
    public static void find(int n, int y, boolean[][] map){
        if(y == n){
            answer += 1;
            return;
        }
        for(int x=0; x<n; x++){
            if(!map[x][y]){
                boolean[][] new_map = new boolean[n][n];
                for(int i=0; i<n; i++){
                    for(int j=0; j<n; j++){
                        new_map[i][j] = map[i][j];
                    }
                }
                find(n, y+1, check(new_map, x, y));
            }
        }
    }
    public static boolean[][] check(boolean[][] new_map, int x, int y){
        for(int i=y; i<new_map.length; i++){
            new_map[x][i] = true;
        }
        int index = 0;
        while(x-index >= 0 && y+index < new_map.length){
            new_map[x-index][y+index] = true;
            index += 1;
        }
        index = 0;
        while(x+index < new_map.length && y+index < new_map.length){
            new_map[x+index][y+index] = true;
            index += 1;
        }
        return new_map;
    }
}