알고리즘 02 재귀함수 응용 | 미로찾기, N-Queens, Backtracking, DFS, 멱집합, 순열, 조합 | JS

protect-me·2021년 8월 27일
DFSN QueensNqueensbinary이미지combinationcountingcelssinablobpermutation깊이우선탐색멱집합모든부분집합미로찾기백트레킹상태공간트리순열조합
0

 📝 CS Study

목록 보기
19/37
post-thumbnail

1. 미로찾기(Decision Problem)

  • 미로찾기 문제 유형 중에서도 출구로 빠져나올 수 있는지 없는지 Decision(Yes or No)을 판단하는 문제
  • 다른 유형으로는 최단거리나 나오는 방법의 수 등이 있을수 있음

function findPath(x, y) {
  if (x < 0 || y < 0 || x >= n || y >= n) {
    return false
  } else if (maze[x][y] !== PATH) {
    return false
  } else if (x === n - 1 && y === n - 1) {
    maze[x][y] = VISITED
    return true
  } else {
    maze[x][y] = VISITED
    if (findPath(x - 1, y) || findPath(x + 1, y) || findPath(x, y - 1) || findPath(x, y + 1)) {
      return true
    }
    maze[x][y] = BLOCKED;
    return false
  }
}

const maze = [
  [0, 0, 0, 0, 0, 0, 0, 1],
  [0, 1, 1, 0, 1, 1, 0, 1],
  [0, 0, 0, 1, 0, 0, 0, 1],
  [0, 1, 0, 0, 1, 1, 0, 0],
  [0, 1, 1, 1, 0, 0, 1, 1],
  [0, 1, 0, 0, 0, 1, 0, 1],
  [0, 0, 0, 1, 0, 0, 0, 1],
  [0, 1, 1, 1, 0, 1, 0, 0],
]
const n = 8
const PATH = 0;
const WALL = 1;
const BLOCKED = 2;
const VISITED = 3;

console.log(maze);
console.log(findPath(0, 0));

미로찾기: 결과확인

  • 어느 방향으로 먼저 진출하느냐에 따라 result maze가 달라짐
  • 2차원 배열이기 때문에 x축, y축과 다르게
    x+1이면 1차원 배열에서 +1
    즉, 프린트된 array에서 아래로 한 칸 가는 것과 동일함
    y+1이면 2차원 배열에서 +1
    즉, 프린트된 array에서 우측으로 한 칸 가는 것과 동일함
if (findPath(x - 1, y) || findPath(x + 1, y)
    || findPath(x, y - 1) || findPath(x, y + 1)) { ... }
[3, 2, 2, 2, 2, 2, 2, 1]
[3, 1, 1, 2, 1, 1, 2, 1]
[3, 2, 2, 1, 2, 2, 2, 1]
[3, 1, 2, 2, 1, 1, 2, 2]
[3, 1, 1, 1, 2, 2, 1, 1]
[3, 1, 3, 3, 3, 1, 2, 1]
[3, 3, 3, 1, 3, 3, 3, 1]
[2, 1, 1, 1, 2, 1, 3, 3]


if (findPath(x, y - 1) || findPath(x, y + 1)
    || findPath(x - 1, y) || findPath(x + 1, y)) { ... }
[3, 0, 0, 0, 0, 0, 0, 1]
[3, 1, 1, 0, 1, 1, 0, 1]
[3, 0, 0, 1, 0, 0, 0, 1]
[3, 1, 0, 0, 1, 1, 0, 0]
[3, 1, 1, 1, 2, 2, 1, 1]
[3, 1, 3, 3, 3, 1, 2, 1]
[3, 3, 3, 1, 3, 3, 3, 1]
[2, 1, 1, 1, 2, 1, 3, 3]


2. Counting Cells in a Blob

  • Binary 이미지
  • 각 픽셀은 background pixel이거나 image pixel
  • 서로 연결된 image pixel들의 집합을 blob이라고 부름
  • 상하좌우 및 대각방향으로도 연결된 것으로 간주

I/O

  • 입력
    : N * N 크기의 2차원 그리드(grid)
    : 하나의 좌표(x, y)

  • 출력
    : 픽셀 (x,y)가 포함된 blob의 크기의
    : (x,y)가 어떤 blob에도 속하지 않는 경우에는 0

Recursive Thinking

현재 픽셀 이 속한 blob의 크기를 카운트하려면
  if 현재 픽셀이 image color가 아니라면
    0을 반환한다
  else 현재 픽셀이 image color라면
    먼저 현재 픽셀을 카운트한다(count = 1)
    현재 픽셀이 중복 카운트되는 것을 방지하기 위해 다른 색으로 칠한다.
    현재 픽셀이 이우한 모든 픽셀들에 대해서
      그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해준다.
    카운터를 반환한다.

solution

function countcells(arr, x, y) {
  if (x < 0 || y < 0 || x >= arr.length || y >= arr.length) {
    // 이미지를 벗어난 경우 return
    return
  } else if (arr[x][y] === 0 || arr[x][y] === 2) {
    // background color 이거나 visited인 경우 return
    return
  } else {
    arr[x][y] = 2 // visited
    count++;
    countcells(arr, x - 1, y - 1)
    countcells(arr, x - 1, y)
    countcells(arr, x - 1, y + 1)
    countcells(arr, x, y - 1)
    countcells(arr, x, y)
    countcells(arr, x, y + 1)
    countcells(arr, x + 1, y - 1)
    countcells(arr, x + 1, y)
    countcells(arr, x + 1, y + 1)
  }
  return count
}

solution v2

function countcells(arr, x, y) {
  if (x < 0 || y < 0 || x >= arr.length || y >= arr.length) {
    return 0
  } else if (arr[x][y] !== 1) {
    return 0
  } else {
    arr[x][y] = 2 // visited
    return (1 
    + countcells(arr, x - 1, y - 1)
    + countcells(arr, x - 1, y)
    + countcells(arr, x - 1, y + 1)
    + countcells(arr, x, y - 1)
    + countcells(arr, x, y)
    + countcells(arr, x, y + 1)
    + countcells(arr, x + 1, y - 1)
    + countcells(arr, x + 1, y)
    + countcells(arr, x + 1, y + 1))
  }
  return count
}

Test

const arr = [
  [1, 0, 0, 0, 0, 0, 0, 1],
  [0, 1, 1, 0, 0, 1, 0, 0],
  [1, 1, 0, 0, 1, 0, 1, 0],
  [0, 0, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 1, 0, 1, 0, 0],
  [0, 1, 0, 1, 0, 1, 0, 0],
  [1, 0, 0, 0, 1, 0, 0, 1],
  [0, 1, 1, 0, 0, 1, 1, 1],
];
const x = 5;
const y = 3;
const n = arr.length
let count = 0;
console.log(countcells(arr, x, y)); // 13


3. N-Queens

상태공간트리 | State-Space Tree

  • 상태공간트리란 찾는 해를 포함하는 트리.
  • 즉 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함
  • 따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음

백트래킹 | Backtracking

백트래킹과 깊이우선탐색

  • 깊이우선탐색 | Deep First Search | DFS
    가능한 모든 경로(후보)를 탐색합니다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못합니다.
    따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것입니다.
    *Recursion 또는 Stack 으로 구현 가능함

  • 백트래킹 | Backtracking
    해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다.
    즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.
    이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다.

    정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것입니다.

주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있습니다.

Design Recursion

if (non-promising) {  
  report failure and return
} else if (success) {
  report answer ans return
} else {
  visit children recursively
}

Solution

function solution(n) {
  let answer = 0;

  const dfs = (board, row) => {
    if (row === n) {
      answer++;
    } else {
      for (let i = 1; i <= n; i++) {
        board[row + 1] = i;
        if (isValid(board, row + 1)) {
          dfs(board, row + 1);
        }
      }
    }
  }

  const isValid = (board, row) => {
    for (let i = 1; i < row; i++) {
      if (board[i] === board[row]) return false;
      if (Math.abs(board[i] - board[row]) === Math.abs(i - row)) return false;
    }
    return true;
  }

  for (let i = 1; i <= n; i++) {
    const board = new Array(n + 1).fill(0);
    board[1] = i;
    dfs(board, 1);
  }

  return answer;
}

*참고2

풀이 참고 : [programmers] Lv3. N-Queens | protect-me



4. 멱집합 | 모든 부분 집합

  • 멱집합 = 주어진 집합의 모든 부분 집합들로 구성된 집합
    ex) [1, 2, 3]의 멱집합
    = [], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]
  • 멱집합의 원소 갯수 = 2^n (n = 주어진 집합의 원소 갯수)
    Why? 주어진 집합의 각 원소를 포함하는 경우, 포함하지 않는 경우의 수를 구함

Solution 1

function powerSet(arr) {
  const flags = new Array(arr.length).fill(0)
  const answer = []

  const dfs = (lv) => {
    if (lv === arr.length) {
      answer.push(arr.filter((v, idx) => flags[idx]))
    } else {
      flags[lv] = 0
      dfs(lv + 1)
      flags[lv] = 1
      dfs(lv + 1)
    }
  }
  dfs(0)
  return answer
}

const arr = [1, 2, 3, 4]
console.log(powerSet(arr));

중간에 flag[lv]는 초기값이 0인데 왜 0을 넣어주었는지 의아할 수 있으나,
다른 가지를 통해 1로 바뀐 상태에서 flags 배열이 넘어왔을 때를 대비해 초기화를 해야함

Solution 2

const subsets = (nums) => {
  const res = [];

  const dfs = (start = 0, arr = []) => {
    res.push(arr);
    if (arr.length === nums) return; 
    for (let i = start; i < nums.length; i++) {
      dfs(i + 1, [...arr, nums[i]]);
    }
  };
   dfs();

  return res;
};

*참고3



5. 순열 | Permutation

  • 순열(nPr): 서로 다른 n개의 물건 중에서 r개를 택하여 한 줄로 세움.
function getPermutations(arr, num) {
  const result = []

  if (num === 1) return arr.map(el => [el])
  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]
    const permutations = getPermutations(rest, num - 1)
    const attached = permutations.map(el => [fixed, ...el])
    result.push(...attached)
  })
  return result
}

const num = 3
const arr = [1, 2, 3, 4]
console.log(getPermutations(arr, num));

6. 조합 | Combination (추가)

  • 조합(nCr): 서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 선택함.
function getCombinations(arr, num) {
  const result = []

  if (num === 1) return arr.map(el => [el])
  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1)
    const combinations = getCombinations(rest, num - 1)
    const attached = combinations.map(el => [fixed, ...el])
    result.push(...attached)
  })
  return result
}

const num = 3
const arr = [1, 2, 3, 4]
console.log(getCombinations(arr, num));


📚 참고

참고1: YOUTUBE | 2015 봄학기 알고리즘 | 권오흠
참고2: [프로그래머스] LV.3 N-Queen (JS) by.longroadhome
참고3: [JS]모든 부분 집합(멱집합) 구하기 by.proshy

Photo by Michael Dziedzic on Unsplash

profile
protect-me
protect me from what i want
이전 포스트

알고리즘 01 재귀함수 기본 | 팩토리얼, 거듭제곱, 피보나치, GCD(최대공약수), 이진탐색) 외 | JS

다음 포스트

알고리즘 03 정렬 기본 | 선택 정렬, 거품 정렬, 삽입 정렬 | JS

0개의 댓글