[프로그래머스] 타겟넘버 (level 2), 깊이/너비 우선 탐색(DFS/BFS)

문제

문제는 위 그림과 같다.
배열의 숫자들을 적잘히 더하고 빼서 만들 수 있는 타겟넘버를 완성하는 경우의 수를 모두 구하는 것.

출처 : https://programmers.co.kr/learn/courses/30/lessons/43165

나의 풀이

onst getCombination = function (arr, seclectNumber) {
  const results = [];
  if (seclectNumber === 1) return arr.map(element => [element]);

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);

    const combinations = getCombination(rest, seclectNumber - 1);

    const attached = combinations.map(element => [fixed, ...element]);

    results.push(...attached);
  });

  return results;
};

function solution(numbers, target) {
  let sum = numbers.reduce((acc, cur) => {
    return acc + cur;
  }, 0)

  var answer = 0;

  for (let i = 1; i <= numbers.length; i++) {
    let combination = getCombination(numbers, i);

    combination.forEach(element => {
      let minus = element.reduce((acc, cur) => {
        return acc + cur;
      }, 0);

      if (sum - minus * 2 === target) answer++;
    });
  }

  return answer;
}

이전에 공부했던 순열을 사용하여 만들어봤다. 하지만 다른 사람의 풀이와 비교했을 때 효율적이지 못했다.

아마도 문제의 제목에 나온 깊이/너비 우선탐색(DFS/BFS)를 사용하여 풀어야 할 듯 하다.

깊이/너비 우선 탐색(DFS/BFS)

1. DFS (깊이우선탐색) 알고리즘이란?

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

• 그래프에서 다른 노드를 방문하기 전에 하나의 노드를 깊게 파고들며 순회하는 검색 알고리즘이다.

• 최상위 노트에서 연결된 자식 노드를 모두 탐색한 후, 더 이상 자식 노드가 없을 때 인접한 상위 노드의 형제 노드를 방문한다. 해당 형제 노드에서도 자식 노드를 탐색하고, 더 이상 자식노드가 없을 경우 다시 인접한 상위 형제의 노드를 방문하는 알고리즘이다.

• 아래 그림을 보면 최상위 루트 노드 (A)에서 (B)를 따라 자식 노드를 탐색한 뒤, (I) 를 가장 마지막에 탐색하게 된다.

• 자바스크립트에서는 재귀 함수를 이용하여 DFS를 구현할 수 있다.
  각각 노드의 자식 노드를 탐색하는 함수를 스택에 추가한 뒤, 더 이상 자식 노드가 없을 때 마지막에 추가된 자식 노드 먼저 실행 후 스택에서 제거하는 후입선출(LIFO) 방식이 이용된다.

• 위 프로그래머스 문제에서 각 노드 (숫자)는 다음 인덱스의 숫자가 (+)인 경우와 (-)인 경우 두 가지의 자식 노드를 가지고 있으며, DFS 방법에 따라 모든 숫자가 (+)인 경우를 모두 탐색한 뒤 다음 인덱스의 숫자가 (-)인 경우를 탐색한다.

function solution(numbers, target) {
  let answer = 0;

  dfs(0, 0);

  function dfs(index, sum) {
    if(index === numbers.length) {
      if (sum === target) {
        answer++;
      }
      return;
    }

    dfs(index + 1, sum + numbers[index]);
    dfs(index + 1, sum - numbers[index]);
  }

  return answer;
}

① 14번 라인 dfs(index + 1, sum + numbers[index]) 부분이 계속 실행되며 다음 인덱스의 숫자가 (+) 인 자식 노드를 계속 탐색한다.

② 마지막 인덱스에 다다랐을 경우(index = 5, sum = 5 일 때) 해당 함수를 스택에서 제거한 뒤, index가 4일 때 15번 라인 dfs(index + 1, sum — numbers[index]) 을 실행하여 (-)인 자식 노드를 탐색한다.

③ 마지막 인덱스에 다다랐으니 다시 해당 함수를 스택에서 제거, index가 3일 때 15번 라인 dfs(index + 1, sum — numbers[index]) 을 실행한다.

④ index 4가 (-)일 때 14번 라인을 실행하여 index 5가 (+)인 경우의 자식을 탐색, 탐색을 마치면 해당 함수를 스택에서 제거한 뒤 15번 라인을 실행하여 index 5가 (-)인 경우의 자식을 탐색한다.

⑤ 다시 index가 2일 때 15번 라인 dfs(index + 1, sum — numbers[index]) 을 실행, index 3이 (-)일 때 14번 라인을 실행하여 index 4가 (+)인 경우의 자식 노드를 모두 탐색 후 15번 라인을 실행하며 index 5가 (-)인 경우의 자식 노드를 탐색한다.

(+)의 자식 노드 탐색 → (-)의 자식 노드 탐색 순서로 위 과정이 진행되며, index 1이 (-)일 때의 자식 노드의 경우의 수 (+), (-) 를 모두 탐색하면 해당 함수가 종료된다.

배열로 위 과정을 살펴보면 아래와 같은 순서로 노드 탐색이 진행된다.

[+1, +1, +1, +1, +1]
[+1, +1, +1, +1, -1]
[+1, +1, +1, -1, +1]
[+1, +1, +1, -1, -1]
[+1, +1, -1, +1, +1]
[+1, +1, -1, +1, -1]
[+1, +1, -1, -1, +1]
[+1, +1, -1, -1, -1]
.
.
.

2. BFS (너비우선탐색) 알고리즘이란?

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
  시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.

• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.
  ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우

  ① 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
  ② 너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색

출처 : [javascript] 프로그래머스 타겟 넘버. 문제 | by 소면(Somyeon) | Medium
[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)