N-Queen

📍 문제 설명

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

💡 접근

이번 문제는 퀸이 어떻게 움직이는지를 몰라서 타 블로그 풀이를 참고했다.

퀸은 상하좌우, 양방향 대각선 한 방향으로 이동할 수 있다.

퀸의 위치를 담는 배열을 하나 선언한다. arr[n] = i -> n열의 i행에 배치시킨다.

 

그리고 0열부터 시작하여 퀸을 배치할 수 있는 모든 경로에 대해서 재귀 호출한다.

모든 열에 배치시킬 때 마다 경우의 수를 증가 시켜주고 리턴한다.

 

👩‍💻 코드

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

public class Main {
    static int n, m, v, e, k, r, x, s, answer, cnt;
    static int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static int[] arr, dice;
    static long[] dp;
    static char[][] board;
    static boolean[][][][] visited;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    static ArrayList<Integer> list = new ArrayList<>();
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n];

        T.solution(0);
        System.out.println(cnt);
    }

    private void solution(int L) {
        //모든 열 다 봤으면(배치 다 시켰으면) 리턴시킨다.
        if(L == n) {
            System.out.println(Arrays.toString(arr));
            cnt++;
            return;
        }

        for(int i = 0; i < n; i++) {
            //L열의 i행에 배치시킨다.
            arr[L] = i;
            //해당 열에 놓을 수 있는 위치일 경우에만 넘어가기
            if(Possibility(L)) {
                solution(L+1);
            }
        }
    }

    private boolean Possibility(int col) {
        //상하좌우, 양방향 대각선으로는 못 놓는다.
        for(int i = 0; i < col; i++) {
            //해당 열의 행과 i열의 행이 일치할 경우 (같은 행에 존재할 경우)
            if(arr[col] == arr[i]) return false;
            //대각선으로 놓여있는 경우
            else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) return false;
        }
        return true;
    }
}