반응형
소개
- 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
- TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
- 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.
문제 & 키워드
- 프로그래머스 - N-Queen (문제 링크)
- 백트래킹
- 재귀
문제 설명
가로, 세로 길이가 n인 정사각형으로 된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
체스판의 가로 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건을 만족하도록 배치할 수 있는 방법의 수를 return하는 solution 함수를 완성해주세요.
제한사항
- 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
- n은 12 이하의 자연수입니다.
입출력 예
| n | result |
| 4 | 2 |
입출력 예 설명
예제 #1
문제의 예시와 같습니다.
문제 접근
이 문제는 백트래킹 알고리즘을 이용해 해결할 수 있습니다. 퀸을 체스판에 배치하는 모든 가능한 방법을 탐색하며, 각 배치가 유효한지 확인하고 유효한 배치를 카운트합니다.
- 배열 초기화
- 퀸의 위치를 저장할 배열을 초기화합니다.
- 백트래킹 함수 호출
- 퀸을 한 행씩 배치하면서 가능한 모든 경우를 탐색합니다.
- 유효성 검사
- 현재 퀸의 위치가 다른 퀸들과 공격할 수 없는 위치인지 확인합니다.
- 카운트 증가
- 모든 퀸을 배치했을 때 카운트를 증가시킵니다.
풀이
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;
}
}
풀이 설명
- 배열 초기화
- 퀸의 위치를 저장할 배열 arr를 초기화합니다.
- 퀸의 개수 n과 답을 저장할 answer 변수를 초기화합니다.
- 백트래킹 함수 호출
- solve 함수는 재귀적으로 호출되며, 각 행에 퀸을 배치합니다.
- depth는 현재 배치할 행을 나타냅니다.
- 유효성 검사
- valid 함수는 현재 배치한 퀸이 다른 퀸들과 공격할 수 없는 위치인지 검사합니다.
- 같은 열에 위치하거나 대각선에 위치한 경우를 검사하여 유효하지 않으면 false를 반환합니다.
- 카운트 증가
- 모든 퀸을 유효한 위치에 배치했을 때 answer를 증가시킵니다.
- solve 함수가 재귀적으로 호출되며 모든 가능한 배치를 탐색합니다.
마무리하며
- 이번 문제를 통해 백트래킹 알고리즘을 활용하여 체스판에 퀸을 배치하는 문제를 해결하는 방법을 학습할 수 있었습니다.
- 재귀 호출을 통해 모든 가능한 배치를 탐색하고, 유효한 배치인지 검사하는 과정으로 문제를 해결했습니다.
반응형
