[DFS/BFS] 타겟 넘버

DFS/BFS 문제를 처음 풀어봤는데

알고리즘 자체는 알고 있었지만 접근 방법이 어려웠다.

 

1. 문제에 대한 접근을 DFS/BFS로 할 수 있다는 것을 떠올리는 게  어려웠고

처음에는 조합 공식을 이용해서 factorial을 재귀함수로 구현해서 풀었다. 하지만 런타임 에러,,,

Time Complexity 문제였던 것 같은데 아직 문제를 풀 때 어떤 알고리즘이 효과적인지 감이 안 오는 것 같다.

Time Complexity 생각하는 것도 다시 한 번 봐야할 듯. 

 

2. 그래프를 나타내는 인접 리스트나 인접 행렬이 주어지지 않은 상태에서 인접 리스트나 인접 행렬을 가정하는 것이 어려웠다.

 

참고로 DFS/BFS 모두 적용하여 만들 수 있긴 하다.

하지만 DFS는 BFS보다 구현이 간단하고 어떤 노드에서 시작해서 다음 분위골 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이기 때문에 해당 문제와 같은 모든 경우의 수 문제에 더 자주 쓰인다. 

 

BFS는 재귀를 사용하는 DFS와 다르게 큐를 사용하여 구현은 더 복잡하다. 하지만 DFS는 두 노드 간의 경로를 찾기에는 적합하지 않다. 인간관계를 예로 든다면 이렇다. A,B,C,D라는 친구가 있을 때 A와 D 친구 간의 접점은 C라는 친구인데 B부터 먼저 탐색하여 B의 모든 인간관계를 다 탐색한 후에 C를 탐색해야지 D를 찾을 수 있다.

 

반대로 BFS와 다르게 인접한 노드를 먼저 탐색하기 때문에 임의의 경로나 최단 경로에 찾는 데에 용이하다.

 

 

풀이방법

문제:

N개의 음이 아닌 정수 배열을 합하거나 더해서 Target number와 같아지는 경우의 수 구하기

 

접근 방법: 

* 합하거나 더하는 것 => 재귀를 통해 모든 경우의 수를 구한다.

* 하나의 숫자를 선택하면 다시 볼 일이 없기 때문에 인접 리스트는 앞에서부터 지워나간다.

* 그래프로 그려보면 다음과 같다.

 

코드를 보면 이진 트리 전위 순회 코드와 굉장히 유사 아니 똑같다.

target과 같을 때의 경우의 수이기 때문에 최종적으로 왼쪽(+cur)과 오른쪽(-cur)의 경우의 수를 합해주어야 한다.  

function dfs(prevsum, prev, numbers, target) {

  let sum = prevsum + prev;
  let cur = numbers[0];

  if (numbers.length === 0) {
    if (sum === target) {
      return 1;
    }
    return 0; // sum != target
  }

  return 
    dfsVisit(sum, cur, numbers.slice(1), target) +
    dfsVisit(sum, -cur, numbers.slice(1), target)
  ;
}

function solution(numbers, target) {
    return dfs(numbers, target);
}

 

아래는

다른 사람 문제 풀이를 보다가 발견한 것.

굉장히 직관적이다. 나도 이런 직관적인 코드 짜고 싶다

 

let sum = prevsum+prev; 이렇게 쓰지 않고 value + numbers[x]를 인수로 사용하여 변수 사용을 줄였고,

solution 함수 안에서 정의하기 때문에 numbers를 인자로 사용할 필요없이 인덱스로만 접근할 수 있다.

또한 이 인덱스를 사용하여 마지막 단계에서 target이랑 비교한다.

 

function solution(numbers, target) {
    let answer = 0;
    getAnswer(0,0);
    
    function getAnswer(x,value) {
    
        if(x<numbers.length){
            getAnswer(x+1,value + numbers[x]);
            
            getAnswer(x+1,value - numbers[x]);
            
        } else{
        
            if(value === target){
                answer++
            }
        }
        
    }
    return answer;
}