Day14

Day14

백트래킹

• 모든 경우의 수를 탐색하는 알고리즘
• DFS나 BFS를 이용할 수도 있다.
• 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는것을 가지치기(Pruning)라고 한다.
• 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다.
  • 코딩테스트에선 이를 고려하여 재귀로 작성해도 풀 수 있도록 문제를 출제하는 경우도 있다.
• 탐색에서 순환(cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다.
• 작성 방법
  1. 모든 경우의 수를 찾는 방법
  2. 특정 조건을 만족하는 경우의 수만 찾는 방법
• 문제 : N-Queen

• 정답코드 ```javascript function check(queen, row) { // 이전까지 두었던 퀸의 위치를 확인한다. for (let i = 0; i < row; i += 1) { // 행의 위치와 대각선의 위치를 체크한다. if (queen[i] === queen[row] || Math.abs(queen[i] - queen[row]) === row - i) { return false; // 둘 수 없다면 false } }

  return true; // 모두 통과되면 true }

function search(queen, row) { const n = queen.length; let count = 0;

if (n === row) { // 체스판 끝에 도달했다면.. 재귀의 탈출 조건 return 1; }

for (let col = 0; col < n; col += 1) { // 0부터 n까지 열을 돌면 둘 수 있게 만든다. queen[row] = col; // 우선 퀸을 둔다 if (check(queen, row)) { // 퀸을 둘 수 있다면.. count += search(queen, row + 1); // 다음 행으로 이동! } }

return count; }

function solution(n) { // 미리 n개 만큼의 배열을 초기화한다. 0번 행부터 시작한다. return search(Array.from({ length: n }, () => 0), 0); }

- 문제 : [네트워크](https://school.programmers.co.kr/learn/courses/30/lessons/43162)
- 정답코드
```javascript
// DFS 함수를 만듭니다.
function dfs(n, computers, visited, start) {
    const stack = [start]; // DFS의 시작점을 미리 초기화 합니다.

    while (stack.length > 0) { // 탐색이 끝날 때 까지 루프를 돌립니다.
        const curr = stack.pop(); // 요소를 하나 뽑습니다.

        visited[curr] = true; // 이미 탐색한 곳은 다음에 탐색을 방지하기 위해 체크합니다.

        for (let i = 0; i < n; i += 1) { // 탐색 가능한 곳을 찾습니다.
            if (!visited[i] && computers[curr][i]) {
                stack.push(i); // 가능하다면 스택에 추가합니다.
            }
        }
    }
}

function solution(n, computers) {
    let answer = 0;
    const visited = new Array(n).fill(false); // 방문한 노드를 기록하기 위한 배열을 선언합니다.

    for (let i = 0; i < n; i += 1) { // 노드 수 만큼 루프를 돌립니다.
        if (!visited[i]) { // 아직 방문하지 않은 곳이 있다면
            dfs(n, computers, visited, i); // 탐색합니다.
            answer += 1; // 영역 하나를 찾았으므로 하나 더해줍니다.
        }
    }

    return answer;
}