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

71654 단어 Nqueens조합순열permutation멱집합깊이우선탐색

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

파일의 N행 데이터를 무작위로 추출하지 않음
[자체 사용 노트] Wine 비트맵 글꼴의 때를 제거하고 WindowsXP에서 복사한 글꼴은 레지스트리로

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage