99클럽 코테 스터디 16일차 TIL + Java Algorithm

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제 & 키워드

• 프로그래머스 - N-Queen (문제 링크)
• 백트래킹
• 재귀

---

문제 설명

가로, 세로 길이가 n인 정사각형으로 된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

체스판의 가로 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건을 만족하도록 배치할 수 있는 방법의 수를 return하는 solution 함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12 이하의 자연수입니다.

입출력 예

n	result
4	2

입출력 예 설명

예제 #1

문제의 예시와 같습니다.

---

문제 접근

이 문제는 백트래킹 알고리즘을 이용해 해결할 수 있습니다. 퀸을 체스판에 배치하는 모든 가능한 방법을 탐색하며, 각 배치가 유효한지 확인하고 유효한 배치를 카운트합니다.

1. 배열 초기화
   • 퀸의 위치를 저장할 배열을 초기화합니다.
2. 백트래킹 함수 호출
   • 퀸을 한 행씩 배치하면서 가능한 모든 경우를 탐색합니다.
3. 유효성 검사
   • 현재 퀸의 위치가 다른 퀸들과 공격할 수 없는 위치인지 확인합니다.
4. 카운트 증가
   • 모든 퀸을 배치했을 때 카운트를 증가시킵니다.

 

풀이

class Solution {

    private int answer, n;
    private int[] arr;

    public int solution(int n) {
        this.n = n;
        arr = new int[n];
        solve(0);
        return answer;
    }

    private void solve(int depth) {
        if (depth == n) {
            answer++;
            return;
        }

        for (int i = 0; i < n; i++) {
            arr[depth] = i;
            if (valid(depth)) {
                solve(depth + 1);
            }
        }
    }

    private boolean valid(int depth) {
        for (int i = 0; i < depth; i++) {
            if (arr[i] == arr[depth]) {
                return false;
            } else if (Math.abs(i - depth) == Math.abs(arr[i] - arr[depth])) {
                return false;
            }
        }
        return true;
    }
}

풀이 설명

1. 배열 초기화
   • 퀸의 위치를 저장할 배열 arr를 초기화합니다.
   • 퀸의 개수 n과 답을 저장할 answer 변수를 초기화합니다.
2. 백트래킹 함수 호출
   • solve 함수는 재귀적으로 호출되며, 각 행에 퀸을 배치합니다.
   • depth는 현재 배치할 행을 나타냅니다.
3. 유효성 검사
   • valid 함수는 현재 배치한 퀸이 다른 퀸들과 공격할 수 없는 위치인지 검사합니다.
   • 같은 열에 위치하거나 대각선에 위치한 경우를 검사하여 유효하지 않으면 false를 반환합니다.
4. 카운트 증가
   • 모든 퀸을 유효한 위치에 배치했을 때 answer를 증가시킵니다.
   • solve 함수가 재귀적으로 호출되며 모든 가능한 배치를 탐색합니다.

 

---

 

마무리하며

• 이번 문제를 통해 백트래킹 알고리즘을 활용하여 체스판에 퀸을 배치하는 문제를 해결하는 방법을 학습할 수 있었습니다.
• 재귀 호출을 통해 모든 가능한 배치를 탐색하고, 유효한 배치인지 검사하는 과정으로 문제를 해결했습니다.