백준 알고리즘 정리 (백트래킹 - 9663번)

황제연·2024년 3월 23일

알고리즘

목록 보기

14/169

문제번호	제목	난이도
9663	N-Queen	골드 4

9663번 N-Queen

해결코드:

import java.io.*;
import java.util.*;

public class Main {

    static int count = 0;
    static int[] arr;
    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 n = Integer.parseInt(br.readLine());
        arr = new int[n];
        backtracking(n,0);


        bw.write(count+"");
        br.close();
        bw.close();
    }

    private static void backtracking(int n, int depth) {
        if(n == depth){
            count++;
            return;
        }


        for (int i = 0; i < n; i++) {
            arr[depth] = i;
            if(nqueen(depth)){
                backtracking(n, depth+1);
            }
        }
    }

    private static boolean nqueen(int now) {
        for (int i = 0; i < now; i++) {
            if(arr[now] == arr[i]){
                return false;
            }

            if(Math.abs(now-i) == Math.abs(arr[now] - arr[i])){
                return false;
            }
        }
        return true;
    }


}

고민의 시간과 해결방법:

체스에서 퀸이 이동할 수 있는 범위는 자신의 상하좌우와 대각선 방향이다
위에서부터 차례대로 퀸을 둔다고 그림을 그려보면 차례대로 아래 행에서 둘 수 있는 퀸의 배치자리는 한정되게 된다.
점점 두다가 내려가다보면 아예 못둬서 그 배치 순서가 끊기는 경우도 존재한다
입력값의 범위가 매우 작기 때문에 재귀로 구현할 수 있다.
또한 재귀의 과정에서 여러 갈래의 경우가 나오므로 재귀함수 안에서 반복문을 써야한다. 따라서 백트래킹으로 해결해야하는 문제이다
정답을 위한 count 변수를 하나 선언하였다. 또한 2차원 배열로도 할 수 있으나 더 쉽고 간결하게 하기 위해 1차원 배열로 배열을 하나 선언하였다
이 배열은 인덱스 번호가 행의 번호이고 그 인덱스의 값이 배치한 열을 의미한다
이제 재귀식을 고민해서 문제 해결을 진행하였다.
함수식은 n과 depth라는 파라미터를 넘겨주었고, n==depth가 되는 순간에 재귀함수를 종료한다
종료할 때는 N-queen 조건이 만족한 것으로 판단하고 count++한뒤 return;으로 종료한다
이제 백트래킹을 진행해야한다. depth가 행이고 순회에서의 i는 열로 판단한다.
처음 행에 놓는 위치에 따라 이후 퀸을 놓을 수 있는 위치는 달라질 것이다. 따라서 모두 순회해야한다
pos[depth] = i를 통해 퀸을 현재 행에 배치한다.
이어서 재귀식인 backtracking(n,depth+1) 실행할지는 이전에 배치한 퀸이 현재 배치한 퀸의 위치에 이동할 수 있는가?를 판단하는 메소드의 boolean return값으로 결정한다
nqueen 메소드는 현재 depth까지 순회를 해서 배치한 퀸의 위치가 현재 행과 같은 곳에 위치해 있는지와 대각선에 위치해있는지를 확인한다
열을 비교하려면 파라미터로 넘어온 depth가 위치한 pos[depth]와 현재 순회중인 pos[i]를 비교하면된다. 같으면 다른행에 자신과 같은 행의 위치한 퀸이 있다는 것이므로 조건을 위배하여 return false를 진행한다
이어서 대각선의 위치에 있는지도 확인한다. 대각선의 위치는 행의 차이랑 열의 차이가 같은 경우이다.
행의 차이는 depth - i를 해주면 되고, 열의 차이는 16번과 같이 해주면 된다.
이때 차이이므로, Math.abs를 통해 한쪽이 커서 발생하는 오류를 해결해준다
만약 같다면 return false를 진행하고 순회를 모두 마치고 나서도 false 리턴을 한다면 이전 퀸 중에 자신이 위치한 퀸의 자리로 이동할 수 있는 것이 없으므로 return true해준다
이 과정을 거친 뒤 완성된 개수를 체크하는 count를 출력하면 정답이 된다.