99클럽 코테 스터디 7일차 TIL : 깊이/너비 우선탐색(DFS/BFS) - 타겟 넘버

DFS랑 BFS가 뭔지 까먹어서 다시 찾아봤다!! 이건 정리해놔야지

대충 자료구조를 트리에 맞춰두고, 거기에 맞게 탐색하는 방법이다.

 

그러니까 문제에서 주어진 number들을 계산사는걸 어케어케 트리로 잘 생각할 수 있어야 하는거다

40분만에 겨우풀었다.. 미들러 문제 목표는 30분내로 푸는거라 많이 부족한것같다 더 노력해야지,,,,,,,,,,,,,,,

---

숫자가 리스트(vector)로 주어지고, 순서를 바꾸지 않고 덧셈과 뺄셈을 적절히 조합하여 target과 같은 결과를 내도록 하는 경우의 수를 찾는 문제였다.

 

이걸 어떻게 tree로 봐야하는지 고민하느라 시간이 많이걸렸는데 내 결론은 이거였다 (틀릴수도 있지만,,,)

만약 숫자 리스트가 [4,1,2,1] 이면

이런 모양의 트리를 생각한다

 

그러면 DFS로 한줄씩 탐색해서 root일 때 최종 sum 결과들을 모은다.

이것들 중 target과 같은게 몇개인지 세면 된다! (BFS로는 안될것같다,, 아마,,?)

 

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

void DFS(vector<int> numbers, int level, int sum, vector<int> &result){
    // level : tree 전체의 레벨, level은 0부터 시작
    // 2진트리니까 왼쪽, 오른쪽만 확인하면됨
    // 지금이 오른쪽이면 자기한테 -붙이기!
    
    
    int now_level = level - numbers.size() + 1;
    if(now_level == level){
        // numbers size가 1일때, 마지막레벨
        // 더이상 확인할게 없음
        // sum에 앞에것들이 누적되어서 들어왔었음! 
        int leftsum = sum + numbers[0];
        int rightsum = sum - numbers[0];
        result.push_back(leftsum);
        result.push_back(rightsum);
        return;
    }
    vector<int> subtree = numbers;
    subtree.erase(subtree.begin()); // 지금 자기자신인 [0]은 sub tree에서 삭제!
    int now = numbers[0];
    // 왼쪽
    int leftsum = sum + now;
    DFS(subtree, level, leftsum, result);
    // 오른쪽
    int rightsum = sum - now;
    DFS(subtree, level, rightsum, result);
    
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    // level이 numbers.size만큼 있는 이진트리
    // 각 레벨 i에는 numbers[i]가 + - + -순서로,,,
    
    int level = numbers.size();
    vector<int> dfs_result;
    
    DFS(numbers, level, 0, dfs_result);
    
    for(int i =0; i<dfs_result.size(); i++){
        if(dfs_result[i] == target){
            answer++;
        }
    }
    
    
    return answer;
}

---

이게맞겠지,,,

일단 풀렸으니까 됐다

DFS랑 BFS나 복습해야겠다.