https://programmers.co.kr/learn/courses/30/lessons/12952
첫 3레벨 문제를 풀어보았다. 첫 문제부터 정말 어려웠다. 특히 내가 몰랐던 backtracking 알고리즘을 새로 배워야 풀 수 있는 문제였다.
backtracking을 간단히 설명하면 DFS 같은 방식으로 탐색을 진행하며 나아갈 때 다음에 도달하는 노드로 인해 정답이 될 수 없는 경우가 발생하면 해당 라인의 탐색은 전부 포기하고 돌아오는 기법을 말한다.
처음 이 문제를 풀 때 2차원 체크 배열을 만들어서 너무 복잡했는데, 풀이를 보니 1차원 배열을 사용하고 있었다. 어차피 퀸은 한 줄에 하나밖에 존재할 수 없으니 1차원 배열의 index 가 column, 각 인덱스의 원소를 row 로 하는 1차원 배열로 체스판 표현이 가능하다.
예를 들어 [1,3,0,2] 이라는 배열이 있다면,
[1,3,0,2]
-------------.
[0,0,Q,0]
[Q,0,0,0]
[0,0,0,Q]
[0,Q,0,0]
이런식으로 표현해주는 것이다.
이런 식으로 사용하는 배열의 장점은 backtracking 으로 인한 초기화를 해줄 필요가 없다는 것이다. 그냥 숫자를 덮어씌우기만 하면 된다. 매우 간단하다.
복습하는 겸 이 문제의 풀이과정을 적어보자. 기본적으로 DFS 와 backtracking 을 가지고 푼다.
for (let i = 1; i <= n; i++) {
let board = Array(n+1).fill(0);
board[1] = i
DFS(board, 1)
}먼저 1부터 n까지 돌면서 퀸을 배치한다. 이때 1차원 배열을 만들어준다. 1부터 시작하는 이유는 0칸이 아니라 1칸부터 시작해서 계산을 편하게 하기 위함이다. 인덱스 0 번은 그냥 비워두고 사용하지 않는다.
DFS 를 통해 해당 칸에 퀸을 배치했을 때 다음 칸에 위치할 수 있는 퀸의 위치를 먼저 검사하고 배치하는 식으로 나아간다.
그 다음은 DFS 함수이다.
function DFS(board, col) {
if (col === n) answer++
else {
for (let i = 1; i <= n; i++){
board[col+1] = i;
if (isPromising(board, col+1))
DFS(board, col+1)
}
}
}만약에 col 이 n과 같아진다면 마지막줄에 퀸을 놓았다는 뜻이고, 이는 퀸을 n개 놓는데 성공했다는 뜻이기 때문에 answer를 하나 올려 준다.
그게 아니라면 다음 column 에 퀸을 배치한다.
만약에
[Q,0,0,0]
[0,0,0,0]
[0,0,0,0]
[0,0,0,0]
이렇게 놓았다면
[Q,Q,0,0]
[0,0,0,0]
[0,0,0,0]
[0,0,0,0]
이렇게 놓는다.
그리고는 isPromising 함수로 유망함, 즉 지금 상태가 유효한지 체크한다. 백트래킹의 핵심이다. 만약 유효하다? 그럼 다시 DFS 를 호출하여 다음 column 에 퀸을 배치한다. 유튜브의 컴공 교수님 수업에서는 이 함수를 유망함이라고 표현하고 promising 이라고 이름 짓던데 isValid로 하는 사람도 있고 이름은 크게 상관없어 보인다.
그럼 유효성 함수를 보자.
function isPromising(board, col) {
for (let i = 1; i < col; i++){
if (board[i] === board[col]) return false;
let colDiff = Math.abs(i-col);
let rowDiff = Math.abs(board[i]-board[col])
if (colDiff === rowDiff) return false;
}
return true;
}이 함수에서 현재 놓은 위치가 유효한지를 검사한다. 그러기 위해서 맨 첫째줄의 퀸부터 시작해서 공격범위에 있는지를 검사한다.
먼저 같은 row 인지 검사한다.
다음 대각선에 있는지 검사한다. 대각선에 있는지 검사하는 방법은 충격적이게도 매우 간단하다. 두 위치 a와 b가 있으면, 두 위치 사이의 가로 거리와 세로 거리가 같으면 대각선에 있는 것이다.
예시)
[Q,0,0,0]
[0,0,0,0]
[0,0,0,0]
[0,0,0,Q]
두 퀸 사이의 가로 거리: 4, 세로 거리: 4 이므로 퀸의 공격 범위에 있음.
그래서 그냥 기존의 퀸의 위치와 검증하고자 하는 퀸의 위치의 row 와 col을 각각 빼서 절대값으로 만들어주면 된다.
이러면 끝난다. 코드 자체는 단순하지만, 1차원 배열의 활용이나 백트래킹 기법을 알아야 풀 수 있는 문제였다.
Full code:
function solution(n) {
let answer = 0;
function isPromising(board, col) {
for (let i = 1; i < col; i++){
if (board[i] === board[col]) return false;
let colDiff = Math.abs(i-col);
let rowDiff = Math.abs(board[i]-board[col])
if (colDiff === rowDiff) return false;
}
return true;
}
function DFS(board, col) {
if (col === n) answer++
else {
for (let i = 1; i <= n; i++){
board[col+1] = i;
if (isPromising(board, col+1))
DFS(board, col+1)
}
}
}
for (let i = 1; i <= n; i++) {
let board = Array(n+1).fill(0);
board[1] = i
DFS(board, 1)
}
return answer;
}