• [9663] 백준 - N-Queen(JAVA)

    2021. 10. 19.

    by. 데롱디롱

    728x90

     

     

    [ 풀이 방법 ]

    - Queen이 이동할 수 있는 것은 다음과 같다.

    👑  Queen의 이동

    - 상, 하, 좌, 우, 대각선의 모든 방향으로 이동 가능하다.
    - 한가지 방향으로 원하는 칸 만큼 이동 가능하다.

    따라서,
    이미 Queen이 배치되어있는 것과 같은 행, 같은 열, 같은 대각선상에 위치하지 않은 자리를 찾아야 한다.

     

     

     

     

    - 한 열에 퀸은 최대 1개밖에 놓일 수 없으므로,
      열 번호를 index, 행 번호를 값으로 가지는 chess 일차배열을 만든다.

    왼쪽 그림과 같이 Queen이 놓인다면, chess에는 오른쪽과같이 행 번호가 저장될 것이다.

     

     

     

     

    - dfs를 돌면서, 다음 Queen이 놓여질 수 있는 곳에 배치를 한다.

    Queen이 놓여질 수 있는 위치 확인

    이제 Queen이 놓여져야 하는 index인 cur을 매개변수로 주어 확인한다.

    1. 앞에 이미 놓인 모든 Queen들의 행이 나와 같지 않아야 함
    2. 앞에 놓인 Queen과 대각선상에 위치하지 않아야 함

     

     

    대각선상에 위치하는지를 체크하는 것은 다음과 같다.

    열의 차이 == 행의 차이
    이면, 이 두 Queen은 같은 위치에 있는 것으로 본다.

    ex) 아래와 같이, 노랑색 위치에 Queen이 놓여질 수 있는지 확인하고 싶은 경우
           두 좌표 (2, 1) 와 (1, 2)의 행과 열의 차이를 비교해본다.
           열 차이 = 2 - 1 = 1
           행 차이 = | 1 - 2 | = 1 
           행과 열의 차이가 같으므로, 두 좌표는 같은 대각선 상에 있는 것이다.

     

     

     

     

    - N개의 Queen 배치가 모두 끝난다면, Cnt를 증가시켜 가능한 경우의 수를 세어준다.

     

     

    - 모든 dfs탐색을 마친 후, Cnt를 출력한다.

     

     

     

     

     

     

    [ 전체 코드 ]

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    public class Main {
    static int N, cnt, chess[];
    public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    chess = new int[N];
    dfs(0);
    System.out.println(cnt);
    }
    private static void dfs(int cur) {
    if (cur == N) {
    cnt++;
    return;
    }
    for (int i = 0; i < N; i++) {
    chess[cur] = i;
    if (isOk(cur)) {
    dfs(cur + 1);
    }
    }
    }
    private static boolean isOk(int col) {
    for (int i = 0; i < col; i++) {
    // 같은 행에 존재하는 경우
    if (chess[col] == chess[i])
    return false;
    // 같은 대각선에 존재하는 경우
    if (col - i == Math.abs(chess[col] - chess[i]))
    return false;
    }
    return true;
    }
    }
    profile
    데롱디롱

    희희.. (๑′ᴗ‵๑)

    댓글