[12952] N-Queen

✔ N-Queen

[프로그래머스 12952]

문제 분석하기

퀸은 좌우, 상하, 대각선을 모두 공격 가능하기 때문에

DFS를 수행하며 해당 위치에 퀸은 놓을 수 있는지 아닌지를 확인하며 경우의 수를 구함

손으로 풀어보기

1. DFS를 수행하며 조건이 맞을 경우 계속해서 퀸을 놓도록 함
   
   • 배치할 자리의 위쪽, 왼쪽 대각선, 오른쪽 대각선들을 모두 확인하며 이미 퀸이 배치되어 있다면 배치 불가능
2. 가능한 경우의 수를 반환

슈도코드 작성하기

n(가로, 세로 길이이자 퀸의 개수)
answer(n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수)
visited(퀸 배치 유무)
dfs(n, 0)
answer 반환 

dfs {
    if(row가 n과 같다면) {
        answer 증가
        return;
    }
    else {
        for(column -> n만큼) {
            if(퀸을 배치할 수 있는지(row, column)) {
                visited[row][column]에 퀸을 배치하므로 true로 변경
                dfs(n, row + 1)
                visited[row][column]을 false로 초기화
            }
        }
    }
}

퀸을 배치할 수 있는지 {
    for(i -> row까지) {
        if(visited[i][column]이 true라면) {
             배치하려고 했던 자리의 위쪽에 퀸이 있으므로 배치 불가능 false 반환
        }
    }
    for(i -> row부터 0이 아닐 때까지, j -> column부터 0이 아닐 때까지) {
        if(visited[i][j]가 true라면) {
            배치하려고 했던 자리의 왼쪽 위 대각선쪽에 퀸이 있으므로 배치 불가능 false 반환
        }
    }
    for(i -> row부터 0이 아닐 때까지, j -> column부터 visited를 벗어나지 않을 때까지) {
        if(visited[i][j]가 true라면) {
            배치하려고 했던 자리의 오른쪽 위 대각선쪽에 퀸이 있으므로 배치 불가능 false 반환
        }
    }
    true 반환
}

코드 구현하기

/**
 * 12952) N-Queen
 */
public class L021_12952 {
    // answer(n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수)
    static int answer;
    // visited(퀸 배치 유무)
    static boolean visited[][];

    // n(가로, 세로 길이이자 퀸의 개수)
    public int solution(int n) {
        answer = 0;
        visited = new boolean[n][n];
        // dfs(n, 0)
        dfs(n, 0);
        // answer 반환
        return answer;
    }

    private void dfs(int n, int row) {
        // row가 n과 같다면
        if (row == n) {
            // answer 증가
            answer++;
            return;
        }
        // row가 n과 같지 않다면
        else {
            for (int column = 0; column < n; column++) {
                // 퀸을 배치할 수 있다면
                if (possible(row, column)) {
                    // visited[row][column]에 퀸을 배치하므로 true로 변경
                    visited[row][column] = true;
                    dfs(n, row + 1);
                    // 다음 배치에는 이 위치에 배치되지 않으므로 visited[row][column]을 false로 초기화
                    visited[row][column] = false;
                }
            }
        }
    }

    // 퀸을 배치할 수 있는지
    private boolean possible(int row, int column) {
        // 배치하려고 했던 자리의 위쪽에 퀸이 있는지 확인
        for (int i = 0; i < row; i++) {
            if (visited[i][column]) {
                // 배치하려고 했던 자리의 위쪽에 퀸이 있으므로 배치 불가능 false 반환
                return false;
            }
        }
        // 배치하려고 했던 자리의 왼쪽 위 대각선쪽에 퀸이 있는지 확인
        for (int i = row, j = column; i >= 0 && j >= 0; i--, j--) {
            if (visited[i][j]) {
                // 배치하려고 했던 자리의 왼쪽 위 대각선쪽에 퀸이 있으므로 배치 불가능 false 반환
                return false;
            }
        }
        // 배치하려고 했던 자리의 오른쪽 위 대각선쪽에 퀸이 있는지 확인
        for (int i = row, j = column; i >= 0 && j < visited.length; i--, j++) {
            if (visited[i][j]) {
                // 배치하려고 했던 자리의 오른쪽 위 대각선쪽에 퀸이 있으므로 배치 불가능 false 반환
                return false;
            }
        }
        // 위쪽, 양쪽 대각선에 모두 퀸이 없다면 퀸을 배치할 수 있으므로 true 반환
        return true;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L021_12952 solution = new L021_12952();

        int n = 4;

        int result = solution.solution(n);

        System.out.println(result);
    }
}