[깊이우선탐색] 프로그래머스 타겟넘버

깊이 우선 탐색(DFS, Depth First Search)은 그래프나 트리 같은 자료 구조에서 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방식의 탐색 기법입니다. 한 번에 한 방향으로 깊이 탐색을 계속하다가 더 이상 탐색할 수 없을 때 이전 경로로 돌아가 다른 경로를 탐색합니다. 이는 재귀적 호출이나 스택을 사용하여 구현할 수 있습니다.

DFS의 특징

• 한 경로를 끝까지 탐색하고 나서 다른 경로를 탐색.
• 순환 구조를 가진 그래프에서 무한 루프에 빠질 수 있기 때문에 방문한 노드를 체크해야 함.
• 재귀적 호출이나 스택을 통해 구현 가능.
• 깊은 노드까지 빠르게 탐색할 수 있으나 최적의 해를 보장하지 않음.

DFS는 모든 가능한 경로 탐색, 백트래킹, 경로 찾기 문제에 자주 사용됩니다. 

 

스택을 활용하는 DFS

function dfs(graph, start, visited) {
  const stack = [];
  stack.push(start);

  while (stack.length) {
    let v = stack.pop();
    if (!visited[v]) {
      console.log(v);
      visited[v] = true;

      for (let node of graph[v]) {
        if (!visited[node]) {
          stack.push(node);
        }
      }
    }
  }
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);
// 0 4 3 2 5 1

 

재귀함수를 활용한 DFS

const dfs = (graph, v, visited) => {
  // 현재 노드를 방문 처리
  visited[v] = true;
  console.log(v);

  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for (let node of graph[v]) {
    if (!visited[node]) {
      dfs(graph, node, visited);
    }
  }
}

const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);
// 0 1 5 2 4 3

 

 

 

프로그래머스 타겟넘버 

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

<제한사항>

- 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.

각 숫자는 1 이상 50 이하인 자연수입니다.

타겟 넘버는 1 이상 1000 이하인 자연수입니다.

이 문제는 numbers 배열의 숫자들을 더하거나 빼는 방식으로 target 값에 도달할 수 있는 경우의 수를 구하는 문제입니다. 주어진 배열을 기반으로 가능한 모든 경우를 탐색하여 원하는 목표 값과 일치하는 경우를 찾아냅니다.

 

 

function solution(numbers, target) {
    let answer = 0;
    getAnswer(0, 0);  // DFS 시작
    
    //함수 getAnswer는 처음에는 인덱스 x = 0과 누적 합계 value = 0에서 시작합니다. 
    //여기서 x는 배열에서 몇 번째 요소를 처리하고 있는지를 의미하고, value는 현재까지의 누적 합계를 나타냅니다.

    function getAnswer(x, value) {
        if (x < numbers.length) {
            getAnswer(x + 1, value + numbers[x]); // 현재 숫자를 더하는 경우
            getAnswer(x + 1, value - numbers[x]); // 현재 숫자를 빼는 경우
            
	// 배열의 인덱스 x가 numbers.length보다 작은 동안, 다음 두 가지 경로를 탐색합니다:
	// numbers[x]를 더하는 경우
	// numbers[x]를 빼는 경우
	// 이 과정을 통해 배열의 모든 요소에 대해 더하거나 빼는 모든 가능한 조합을 탐색합니다.
    
        } else {
            // 배열의 끝에 도달한 경우
            if (value === target) {  // 최종적으로 계산된 값이 target과 같다면
                answer++;  // 경우의 수 증가
            }
            
        // 배열의 끝 (x === numbers.length)에 도달하면, 현재까지의 value가 target과 일치하는지 확인합니다. 
        // 일치한다면 answer를 1 증가시킵니다.
        }
    }
    
    return answer;  // 최종적으로 target을 만족하는 경우의 수 반환
}

 

 

DFS를 사용하여 주어진 numbers 배열의 각 요소를 더하거나 빼는 방식으로 가능한 모든 경우의 수를 탐색합니다.

배열의 끝에 도달할 때마다 value가 target과 같은지 확인하고, 같다면 경우의 수를 증가시킵니다.