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

 

 

[ 풀이 방법 ]

- 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;
    }
}