🎯문제
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
제한사항
- 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
- n은 12이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 4 | 2 |
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
✏️풀이
코드
class Solution {
int[] col;
int answer;
// 현재 위치에 놓을 수 있는지 판단하는 메서드
public boolean possible(int depth) {
for(int i = 0; i < depth; i++) {
// 같은 직선과 대각선에 위치하는지 확인
if(col[i] == col[depth] || Math.abs(depth - i) == Math.abs(col[depth] - col[i])) {
return false;
}
}
return true;
}
// dfs 탐색 메서드
public void dfs(int n, int depth) {
// 모든 Queen을 놓았을 경우
if(n == depth) {
answer++;
return;
}
for(int i = 0; i < n; i++) {
// 위치를 옮겨가며 Queen을 놓아줌
col[depth] = i;
// 놓을 수 있는지 확인
if(possible(depth)) {
// 놓을 수 있다면 탐색 진행
dfs(n, depth + 1);
}
}
}
public int solution(int n) {
answer = 0;
col = new int[n];
// 탐색 시작
dfs(n, 0);
return answer;
}
}설명
dfs 탐색의 방식으로 진행하였다.
possible 메서드는 현재 위치에 놓을 수 있는지 판단하는 메서드이다. 매개변수로는 depth만 가진다. 반복문을 통해 확인을 하는데 같은 행에 있거나 대각선에 위치하는지를 확인하고 하나라도 해당이 된다면 false를 return 해준다.
예를 들어, col[0] = 1이고 col[1] = 0일 경우는 첫번째 열의 두번째 행에 Queen이 존재하는 것이며 두번째 열의 첫번째 행에 Queen이 존재하는 것이다. 이렇게 했을 경우 같은 행에 존재하지 않으므로 첫번째 조건에는 해당하지 않는다.
두번째 조건은 대각선에 위치하는지 확인하는 것으로 대각선에 위치하는 것은 기울기를 통해 확인할 수 있다. col[0] = 1이고 col[1] = 0일 때 |1 - 0| = |0 - 1|이므로 대각선에 위치한다는 것을 알 수 있다.
dfs는 dfs 탐색 메서드로 n과 depth를 매개변수로 가진다. depth는 깊이를 뜻하며 깊이가 깊어질수록 Queen의 개수가 증가한다는 뜻이다. 때문에 n개의 Queen을 놓아야하는 조건을 만족하기 위해서 n == depth일 때 탐색을 종료한다. 이때 answer의 값을 증가시키고 탐색을 종료한다.
만약 조건에 만족하지 않는다면 계속해서 탐색을 진행한다. 위치를 옮겨가며 Queen을 놓아주는데 이때 놓을 수 있는지 possible 메서드를 사용하여 확인해준다. 만약 놓을 수 있다면 dfs 탐색을 이어간다.
col 배열은 열을 뜻하며 col[0] = 2는 첫번째 열, 세번째 행에 Queen을 놓는다는 뜻이다. 이후 dfs를 진행하면 col[1]이 되고 이는 두번째 열에 Queen을 놓는다는 뜻이다. 즉, 열별로 탐색을 진행하며 해당 열에 어느 위치에 Queen을 두고 다음 열에 Queen을 또 두고 이런 식으로 깊이 탐색을 진행하는 방식이다.
이런 식으로 모든 반복이 끝나고 나온 answer를 반환해주면 문제를 해결할 수 있다!
💡느낀 점
깊이 탐색 문제는 여러번 풀어봐서 쉽게 풀 수 있을거라 생각했지만 행과 열을 생각하는 부분에서 헷갈렸다. 문제를 풀면서 이 문제는 블로그에 꼭 작성해야겠다고 생각했는데, 문제 자체가 어렵기도 하고 코드의 방식이 단숨에 이해가 되는 방식이 아니라고 생각했기 때문이다. 나 역시 블로그를 쓰면서 다시 한 번 이해를 할 수 있었다.. 문제의 정답만 맞으면 끝이 아니라 이런 식으로 코드 리뷰하는 시간을 통해 더 많은 공부가 되는 것 같다. 블로그를 열심히 써야겠다..^^
링크
