[SWEA] dfs/백트래킹 - 2806번 N_Queens 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

 

바빠서 자세한 풀이는 생략..

전에 풀어본 코어문제?랑 좀 비슷했다

 

풀이코드

package D3;

import java.io.*;

public class N_Queens { //swea n-queens 문제
    static int[][] board;
    static int N;  //N*N크기의 보드에 N개의 퀸들을 놓을것임
    static int[] dirx = {0, 0, -1, 1, -1, 1, -1, 1}; //상하좌우대각선(왼쪽위,오른쪽위,왼쪽아래,오른쪽아래) 탐색
    static int[] diry = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int count;   //가능한 경우의 수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());    //테스트 케이스 수

        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());
            board = new int[N][N];
            count = 0;
            dfs(0, 0);
            bw.write("#" + t + " " + count);
            bw.newLine();

        }
        bw.flush();
        bw.close();
    }
    static void dfs(int depth, int col) {
        if (depth == N) {
            count++;
            return;
        }
        for (int i = 0; i < N; i++) {   //한 행에서 놓을수 있는 경우를 본다
            if (findAllDir(col, i)) {     //놓을수 있는 경우라면
                board[col][i] = 1;
                dfs(depth + 1, col + 1);
                board[col][i] = 0;  //이부분을 안했었다!!
            }
        }
    }

    static boolean findAllDir(int col, int row) {   //현재 놓으려는 위치가 유망한지 알아보는 함수
        int tmpC; int tmpR;
        for (int i = 0; i < 8; i++) {
            tmpC = col;
            tmpR = row;
            while (tmpC >= 0 && tmpC < N && tmpR >= 0 && tmpR < N) {
                if (board[tmpC][tmpR] != 1) {   //가려는 위치에 이미 퀸이 놓여있는게 아니라면
                    tmpC = tmpC + diry[i];
                    tmpR = tmpR + dirx[i];
                } else {    //1이 있다면 실패
                    return false;
                }

            }
        }
        return true;
    }
}