190926 N queens problem
이번 sprint의 과제는
- n x n 체스보드가 주어졌을 때, n개의 rooks가 서로 공격하지 않도록 어떻게 놓을 수 있을까요?
- n x n 체스보드가 주어졌을 때, n개의 rooks가 서로 공격하지 않게 놓을 수 있는 방법들엔 몇 가지가 있을까요?
- n x n 체스보드가 주어졌을 때, n개의 queens가 서로 공격하지 않도록 어떻게 놓을 수 있을까요?
- n x n 체스보드가 주어졌을 때, n개의 queens가 서로 공격하지 않게 놓을 수 있는 방법들엔 몇 가지가 있을까요?
n을 파라미터로 받아서 위 네개의 메소드를 구성하는 것이다.
모든 말들은 모두 서로에게 적대적이다. (=이동범위에 겹치면 안된다)
시각적으로 이해를 해보자.
n이 3을 받은 경우, 생성되는 Board객체의 모습이다.
표현은 2차원배열로, board [[0,0,0],[0,0,0],[0,0,0]]이렇게 표현할 수 있다.
이 상태에서 board[0][0]의 값을 1로 변경시킨다.
board [[1,0,0],[0,0,0],[0,0,0]]
그림으로 보면 이렇게 된다.
룩을 두었다고 생각하면, 룩을 기준으로 종횡 모두 말 배치가 불가능한 자리가 된다.
따라서 그 다음 행으로 넘어가서,
해당 행에 놓을 수 있는 경우의 수를 보자.
빨간색 두 자리가 배치가 가능하다. 그리고 각각의 경우에 따라,
그 다음행에 한 자리만 놓을 수 있게 된다.
따라서 3*3의 판에 3개의 룩을 배치할 수 있는 경우의 수는
1행에서 3 / 2행에서 2 /3행에서 1 → 3! 이 된다.
이것을 보면 트리탐색의 로직과 비슷해 보인다.
조건에 따라 가지를 치며 경우의수를 줄여가며 해당 조건에서 가능한 바로 다음 수들을 탐색하는 것이다.
(따라서 트리탐색의 개념과 용어를 가져와서 이후 서술한다. 트리탐색은 이전 포스팅을 확인)
- 최종 기보는 마지막 줄에서 마지막 룩을 놓은 상태에서 서로 공존이 가능한지 체크
2. COUNT++ 하거나 , 기보자체를 저장
3.이후 트리탐색과 같이 리프에서 상위 노드로 올라가 다음 리프로 진행.
퀸 배치
퀸의 경우 룩의 공존 규칙에 대각선의 방향 2가지 (MAJOR와 MINOR로 구분하겠다.) 조건을 추가해주면 기본적인 구조는 동일하다.
이 때, 대각선에 말이 존재하는지 체크하기 위해서는 starting point가 필요한데, Minor Diagonal을 기준으로 보면, 숫자 3의 자리포함 왼쪽에 위치한 1행의 값들은 starting포인트로 모두 활용이 가능하다. 그러나 3–9–2–5 의 오른쪽에 해당하는 값들은 체크가 불가능하다. 그렇기 때문에,
1–4–7–3까지 0행에서 0,1,…3번째 값까지, 그리고 거기부터는 starting포인트가 아래로 떨어진다.
그렇기 때문에 크게 두가지로 구분하여 스타팅포인트를 다르게 잡고, 다르게 이동시키며 동일한 검증 로직을 실행시키면된다.
Major Diagonal의 경우도 그러한 방식을 이용한다.
Rook을 NxN에 N개 공존시킬 수 있는 기보의 수 :
n을 파라미터로 먼저 받는다NxN 빈 보드를 만든다.재귀함수를 만든다.재귀함수 실행(시작보드,시작row)return 누적 count — — 이렇게 종료가 된다.
여기서 재귀함수가 하는 동작은
-파라미터로 받은 보드[시작row]의 열들을 기준으로 forEach를 돌린다.
-특정 자리 진입 후, 보드를 deep카피하여, 배치전 copyBoard를 만든다.
-해당 자리의 값을 0에서 1로 변경한다 (룩을 놓는다)
-말을 추가한 copyboard의 유효성을 위에서 만든 checkMethod를 통해 확인
— 통과할 시,
말을 놓은 행이 마지막 행인지 확인 -> 그렇다면 cnt++ 해주고 해당 leaf종료
->마지막 행이 아니다? recursive(현재상태보드,시작rowIndex+1)
재귀함수내에 return문이 없으므로,
전체 forEach문이 종료 된 후,
누적된 메소드변수 누적cnt를 최종 return 하면 종료가 된다.
여기서 board를 카피하는 동작은
백트래킹을 위해서이다. (충돌발견 -> 성공직전 상태로 돌림)
카피를 하지 않고 원본board를 대상으로 모든 leaf까지의 작업을 진행하게 되면, 상위 노드에서의 작업할 때, 이전 leaf에서의 변경사항이 반영이 되어있다.
여기서 copy할 때 주의해야 할 점이 있는데,
데이터주소만 참조하는 shallow copy 가 아닌, 데이터 자체를 떠오는 독립적인 사본을 만드는 deep copy를 만들어야 하는 것이다.
이때, Array.prototype.slice()의 경우, 1차원 array (ex. [1,2,3])의 경우는 deepcopy가 되지만, 그 이상 차원의 배열의 경우 shallowCopy를 하게 되어, 복사의 의미가 없어지게 된다.
따라서 본인의 경우, JSON.stringify를 한 다음에 다시JSON.parse로 array로 만드는 방식을 해보았는데, 시간복잡도가 큰 방식이라,
복사할 array = arr,
copied = arr.map(function(value){return value.slice});
이런식으로 2차원 배열을 1차원 배열단위로 slice()한 값으로 구성된 2차원 배열을 저장했다.
재귀관련 이슈
function loop(n){
console.log(‘loop시작이야’,n)
if(n>0){
console.log(‘양수’,n);
return n;
}
loop(++n); //return loop(++n);
}test = loop(0);
test === undefined
loop(1)실행 -> 조건문진입 -> return 1 근데 왜 안저장?
그 이유는 재귀로 자신을 호출 할 때, return이 아니라 실행문으로 호출하게 되면 해당 return값은 무언가 어딘가로 날라감. return으로 해당 실행문의 return값을 받아서 return해줘야 함.
backtracking을 위해서 특정 leaf가 원하는 값이 아니면,
다시 상위 노드로 올라가 재귀를 진행해야 하는데, 안돌아가는 경우가 있다.
그 이유는 이미 return으로 인해 종료가 되는 경우이다.
let standard = recursive(newBoard, rowIndex + 1);if (JSON.stringify(standard) !==
JSON.stringify(new Board({n}).rows())) {return standard;}
이러한 경우를 막은 예시들이다.
standard는 다음 행을 대상으로 진행하는 재귀이다.
if()안에서 재귀를 실행한 다음, return이 빈 보드인지 판단을 하고,
아닌 경우에만, 해당 재귀를 실행한다.
만약 이 if문이 없다면, leaf에 도착했을 때, 그대로 종료하게 된다.
아래는 트리에 해당 value property를 가진 node가 있는지 확인하는
재귀함수이다.
treeMethods.contains = function (target) {
if (this.value === target) {
return true;
} else {
if (this.children.length !== 0) { // value 틀리고 자식이 있을 때, for (let key in this.children) { if(this.children[key].contains(target)){
return true;
}
}
}
}
return false;};여기서도
if(this.children[key].contains(target)){
return true;
}재귀를 if문안에서 실행하는데,
이 경우에도 그냥 해당 method를 return을 하게 된다면,
leaf에 도착한 경우 false를 리턴받아 다시 해당 false를 return한다.
