[프로그래머스] Level 3. 양과 늑대

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

 

이진트리 탐색으로 모든 경우의 수를 탐색하고, 그 중 양이 제일많은 경우를  찾는 문제이다.

이 문제가 진짜 어려웠던 것은, visited했던 곳도 나중에 다시 찾아야 한다는 점이다. 한마디로 자신의 삼촌이나 조카노드까지 다시 검사를 해야한다.  내 아래에있는 자식들까지 모두 검사를 했다면, 내조카, 삼촌들을 위해서 visited = false로 변경해주는것이 핵심인 문제이다. 

 

 

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

using namespace std;

vector<vector<int>> childs;
vector<int>  visited;

int answer;

void dfs(const vector<int>& info, vector<int> cur){
    int sheep =0, wolf =0;
    for(auto c : cur){
        if(info[c] == 1) wolf ++; 
        else if(info[c]==0) sheep ++;
    }
    
    if(sheep <= wolf) return;
    answer = max(answer, sheep);
    
    for(int i=0; i<cur.size(); i++){
        int node =cur[i];
        for(int c : childs[node]){
            if(visited[c]) continue;
            visited[c] = true;
            cur.push_back(c);
            dfs(info,cur);
            cur.pop_back();
            visited[c] = false; // 다른 dfs에서 나를 다시 검사할수있게끔. 
        }
    }
    
    
}
int solution(vector<int> info, vector<vector<int>> edges) {
    //자식노드 정보 넣기
    visited.resize(info.size(),false);
    childs.resize(info.size());
    for(int i=0; i<edges.size(); i++){
        childs[edges[i][0]].push_back(edges[i][1]);
    }

    visited[0] = true;
    dfs(info,{0});
    
    return answer ;
    
}

 

 

마무리하며

사실 완벽하게 이해한 것 같지 않다. BFS로도 풀 수 있다고 하는데, 아~ 도전해볼 용기가~~ 나지~않는다~

내일해보자 내일..