2806 N-Queen

N-Queen URL

Solution 1

import java.io.*;

public class SW2806 {
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int[][] graph;
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());
            graph = new int[N][N];
            result = 0;
            dfs(0);
            sb.append("#").append(t).append(" ").append(result).append("\n");
        }
        System.out.println(sb);
    }

    static void dfs(int row) {
        if (N == row) {
            result++;
            return;
        }

        for (int col = 0; col < N; col++) {
            if (isPromising(row, col)) {
                graph[row][col] = 1;
                dfs(row+1);
                graph[row][col] = 0;
            }
        }
    }

    static boolean isPromising(int currentRow, int currentCol) {
        //수직 체크
        for (int r = 0; r < currentRow; r++) {
            if (graph[r][currentCol] == 1) {
                return false;
            }
        }

        //좌 대각선 체크
        for (int r = currentRow-1, c = currentCol-1; r >= 0 && r < N && c >= 0 && c < N; r--, c--) {
            if (graph[r][c] == 1) {
                return false;
            }
        }

        //우 대각선 체크
        for (int r = currentRow-1, c = currentCol+1; r >= 0 && r < N && c >= 0 && c < N; r--, c++) {
            if (graph[r][c] == 1) {
                return false;
            }
        }
        return true;
    }
}

이 Solution은 2차원 배열을 생성하고 행마다 dfs탐색을 돌며 한 행에 하나의 퀸을 배치하고 마지막 행에 배치되면 result를 1증가시켜주는 방식이다. dfs을 돌 땐 isPromising메서드를 타고

1. 수직
2. 좌 대각선
3. 우 대각선

을 체크하여 공격범위에 있다면 false 그렇지 않다면 true를 리턴한다.
flase가 리턴될 경우 놓을 수 없는 자리이므로 graph[row][col] = 0으로 초기화 하여 백트래킹을 진행한다.

Solution 2

import java.io.*;

public class SW2806 {
    static StringBuilder sb = new StringBuilder();

    static int[] graph;
    static int answer;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());
            graph = new int[N];
            answer = 0;
            dfs(0);
            sb.append("#").append(t).append(" ").append(answer).append("\n");            
        }
        System.out.println(sb);
    }

    static void dfs(int row) {
        if (N == row) {
            answer++;
            return;
        }
        for (int col = 0; col < N; col++) {
            graph[row] = col;
            if (isPromising(row)) {
                dfs(row+1);
            }
        }
    }

    static boolean isPromising(int currentRow) {
        for (int r = 0; r < currentRow; r++) {
            if (graph[r] == graph[currentRow]) {
                return false;
            }

            if (Math.abs(r-currentRow) == Math.abs(graph[r] - graph[currentRow])) {
                return false;
            }
        }
        return true;
    }
}

1차원 배열을 사용해서 풀이하는 방식으로 각 인덱스를 열로 생각하면 풀이해야하는데 아직 이해가 부족한 방식이므로 2차원 배열로 풀이하였다.

배운점

백트래킹 문제는 나올 때 마다 헷갈렸던것 같다.
완전탐색문제를 완벽히 이해하며 풀이하는데 백트래킹은 모르고 넘어가선 안되는 문제라고 생각하여 하루 이상의 시간동안 고민하고 방법을 찾아보았다.
비슷한 문제가 나왔을 때 풀 수 있도록 복습이 필요할것같다.