백준 9663. N-Queen

어떻게 운 좋게 sds 알고리즘 특강 참여하고 있는데........
1일차 알고리즘 기초 배우면서 풀었던 첫번째 문제.
당일날 못풀어서, 어찌저찌 오늘 풀고 작성한다.

문제 : 백준 9663. N-Queen

N의 입력을 받아서 체스판에 N개의 퀸을 두는데, 서로 공격할 수 없는 위치에 두어야 한다. N개의 퀸을 두는 경우의 수를 구하는 프로그램을 작성해야 한다.
N개의 퀸을 놓을 수 없는 경우라면 불필요한 탐색은 필요하지 않으니, 이러한 조건을 먼저 걸고 탐색을 진행하기 때문에 백트랙킹으로 해결할 수 있다.

문제 해설을 듣기 전에 내가 생각한 풀이는 다음과 같다.
방법 1. n x n 의 배열 모든 곳에 퀸을 두면서 모든 경우의 수를 살피려 했다.
방법 2. n x n 배열을 탐색하면서 해당 행, 열에 있으면 퀸을 못놓는 경우를 이용하여 구현

내가 생각했던 풀이는 1번이고, 2번은 강사님께서 이러한 방법으로 구현하겠죠? 라고 하셨던 방법이다.

두 방법 모두 TLE 난다고 하신다.

아래와 같은 풀이를 알려주셨다.

1. 한 행에는 하나의 퀸만 놓을 수 있으니 for문 하나만 돌면서 행마다 하나의 퀸을 놓는다.
2. 퀸이 놓인 열은 방문 처리
3. 대각선 위치에 퀸의 유무를 통한 방문 처리

[n][n]행렬을 생성할 필요도 없이 배열 3개만으로 처리가 가능한다.

대각선 방문 처리가 이해가 안될 수도 있는데, 그림으로 그려서 표현하고 싶지만, 마우스가 현재 없으므로 스킵.

/*
백준 9663. n-queen
 */
package Day1_Algorithm_Basic;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class boj9663 {

    static int cnt, n;
    static int[] visit_y;  // 열의 퀸 유무 체크 배열
    static int[] visit_l;  // 왼쪽 방향으로 내려가는 대각선 퀸 유무 체크 배열
    static int[] visit_r;  // 오른쪽 방향으로 내려가는 대각선 퀸 유무 체크 배열

    static void back(int x) {
        // 행 x의 값이 n인 경우, 즉 체스판 가장 아래까지 퀸이 배치된 경우 경우의 수를 증가시키고 종료
        if (x == n) {
            cnt++;
            return;
        }
        
        // x번째 행의 y번째 열을 탐색
        for (int y = 0; y < n; y++) {
            // 순서대로 열, 대각선 오, 왼 방향의 퀸 유무 확인
            if (visit_y[y] == 0 && visit_r[x - y + (n + 1)] == 0 && visit_l[x + y] == 0) {
                visit_y[y] = 1;
                visit_l[x+y] = 1;
                visit_r[x - y + (n + 1)] = 1;
                back(x + 1); // 퀸 유무 확인 후, 다음 행 탐색
                visit_y[y] = 0;
                visit_l[x+y] = 0;
                visit_r[x - y + (n + 1)] = 0;

            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        visit_y = new int[n];
        visit_l = new int[2 * n + 1];
        visit_r = new int[2 * n + 1];

        back(0);
        System.out.println(cnt);

    }
}