[Java] 백준 9663번 : N-Queen <Gold 4>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

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

9663번: N-Queen

Code

---

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

public class Main {
    boolean[][] visited;
    int N;
    int count = 0;

    void run() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        visited = new boolean[N][N];

        DFSUtil();

        System.out.println(count);
    }

    void DFSUtil(){
        for(int i = 0; i<N;i++){
            visited[i][0] = true;
            DFS(1);
            visited[i][0] = false;
        }
    }

    void DFS(int line){
        if(line < N) {
            for (int i = 0; i < N; i++) {
                if (!visited[i][line]) {
                    if(rowCheck(i) && columnCheck(line) && diagonalCheck(i, line)) {
                        visited[i][line] = true;
                        DFS(line + 1);
                        visited[i][line] = false;
                    }
                }
            }
        }else{
            count++;
        }
    }

    boolean rowCheck(int y){
        for(int i = 0; i < N; i++){
            if(visited[y][i]){
                return false;
            }
        }
        return true;
    }

    boolean columnCheck(int x){
        for(int i = 0; i < N; i++){
            if(visited[i][x]){
                return false;
            }
        }
        return true;
    }

    boolean diagonalCheck(int x, int y){
        int xx = x;
        int yy = y;

        //우측상단
        while(xx >= 0 && yy < N){
            if(visited[xx][yy]){
                return false;
            }
            xx--;
            yy++;
        }

        //우측하단
        xx = x;
        yy = y;
        while(xx < N && yy < N){
            if(visited[xx][yy]){
                return false;
            }
            xx++;
            yy++;
        }

        //좌측상단
        xx = x;
        yy = y;
        while(xx >= 0 && yy >= 0){
            if(visited[xx][yy]){
                return false;
            }
            xx--;
            yy--;
        }

        //좌측하단
        xx = x;
        yy = y;
        while(xx < N && yy >= 0){
            if(visited[xx][yy]){
                return false;
            }
            xx++;
            yy--;
        }

        return true;
    }


    public static void main(String[] args) throws IOException{
        Main my = new Main();
        my.run();
    }
}

---

Code 필수 요소

1. 백트래킹 활용

2. Queen이 놓아질 수 있는 조건 탐색

 

이것만 생각해내면 절반은 끝났다.

 

// 백트래킹 활용

이번 문제는 백트래킹을 사용했다.

Queen이 놓아질 수 있는 자리인지 확인하고, 놓아질 수 없다면 이전 단계로 돌아가 다시 자리를 탐색하는 방법을 사용했다.

사실상 백트래킹의 대표격인 문제이다보니 백트래킹의 원리를 그대로 사용해서 풀 수 있었다.

 

// Queen이 놓아질 수 있는 조건 탐색

먼저 Queen은 가로, 세로 대각선 모두 움직일 수 있는 말이기 때문에 전부 다 탐색해야 한다.

가로를 탐색해서 해당 위치에 다른 말이 존재하는지 확인하고, 세로도 같은 방법으로 탐색한다.

여기서 문제는 대각선이다.

모든 부분을 확인해야 하기 때문에 좌측상단, 좌측하단, 우측상단, 우측하단 네 부분을 전부 확인해 준다. 

값을 변경시켜가며 대각선 위치를 확인해주고 범위를 벗어나지 않도록 설정해 주었다. 

 

// 전체적 설명

값을 입력받아 해당하는 크기의 체스판을 만들어 주고, visited배열을 만들어준다. 체스판의 세로 줄을 하나씩 탐색하며 해당 위치에 Queen이 올 수 있는지 확인한다. 그 후 마지막 줄에 Queen이 들어갔다면 count를 ++시켜줘 총 몇개의 경우의 수가 있는지 파악한다. 

 

 

이것도 생각보다 간단했다. 이전에 풀어왔던 알고리즘 문제들이 슬슬 도움이 되어가는 느낌. 난이도가 골드인거에 비해 확실히 해결하는데 드는 시간이 줄었다. 예전에 실버 2정도 푸는 느낌?

물론 돌아가는 코드를 만드는 속도일 뿐이다. 아직도 최적화된 코드는 어렵다...

-꿑-