📌 N-Queens?
N-Queens은 백트래킹 알고리즘 문제로 유명한 문제이다. 문제의 간단한 룰은 이러하다.
임의의 n의 숫자가 주어지면 n^2크기로 만들어진 체스판이 생긴다. 체스판 위엔 서로 공격할 수 없도록 n개의 퀸을 올려두는 경우의 수를 구하는 문제이다. 퀸은 체스에서 자신의 상하좌우, 그리고 대각선방향으로 공격할 수 있고 움직임에 제한된 횟수는 없다. 아래 이미지는 n이 4인 예이다.
Backtracking 알고리즘
재귀에 기반한 문제 해결방법 중 하나이다. Backtracking은 크로스워드, 구두연산, 스도쿠 및 기타 여러퍼즐과 같은 제약 조건 만족 문제를 해결하는데 중요한 방법이다. Backtracking의 예로 미로가 있다고 가정하고 출구 찾는 것을 확인하는 방법을 생각해보자. 출구를 찾아 움직이다가 막다른 길에 다다르면 다시 처음 갈림길이 있던 자리로 되돌아가서 다른 루트로 시작을 한다. 이러한 방법을 반복해서 미로에서 나오게 된다. 이러한 일련의 과정이 Backtracking이다. 일반적으로 문제를 해결하려면 지수시간이 걸린다. 하지만 Backtracking으로 최적화로 생각할 수 있다. 깊이우선탐색은 기본적으로 Backtracking개념을 사용한다.
깊이우선탐색 (DFS)
넓게 탐색하기 전 깊은곳을 먼저 탐색하는 방법이다. 너비 우선 탐색보다 간단하지만 검색속도는 상대적으로 느리다. 모든 방법을 탐색하며 자료구조 중에서 스택(Stack)을 사용한다.
너비우선탐색 (BFS)
깊게 탐색하기 전 넓게 탐색하는 방법이다. 최단 경로 혹 이의의 경로를 찾고 싶은 경우 많이 사용된다. 재귀적으로 동작하지 않고 자료구조 중에서 큐(Queue)를 사용한다.
🤔 너비우선탐색으로 N-Queens 생각해보기
구글링을 하면 깊이우선탐색으로 N-Queens를 구현하는 과정은 많이 있지만 너비우선탐색은 비효율적이고 복잡하다보니 자세한 내용이 없어서 나름대로 생각을 해서 정리하기로 했다. 이것은 혼자서 생각하고 정리한 정보이다 보니 정확하지 않음을 미리 전달한다. 단순히 나의 생각을 정리하는 것이다.
n의 값이 3이라고 가정했을때 체스를 코드로 표현하면 아래와 같다.
let chess = [[0,0,0],[0,0,0],[0,0,0]]
// [ [0,0,0],
// [0,0,0],
// [0,0,0] ]
// (0, 0), (0, 1), (0, 2)
// (1, 0), (1, 1), (1, 2)
// (2, 0), (2, 1), (2, 2)- 너비우선탐색방법(BFS)은 재귀를 사용하지 않으니 처음 시작하는 위치를 정한다.
- 반복문을 이용해 배열의 갯수만큼 돌고 반복문을 한번 더 이용해 2차배열까지 접근한다.
for(let i =0; i<n; i++){
for(let j =0; j<n; j++){
//충돌확인함수(arr[i][j])
}
}
// 처음 시작점을 제외하는 방법은 조건문을 이용한다- 기준을 제외한 모든 값을 충돌발생여부를 확인한다.
- 충돌이 발생하지 않으면 value를 1더한다.
