22.06.15. 풀었던 문제들

1. 양과 늑대

처음에는 현재 미탐색인 양으로부터 visited까지 올라오면서 추가 가능한 양들만 계속 탐색해 나갈려고 했는데 너무 복잡해졌다. 조금 검색해서 DFS란 걸 알았고 이걸 아니까 쉽게 풀리는 문제였다.

먼저 candidates vector는 현재까지 visited인 것들의 child vector이다. 즉, 탐색 가능한 후보군 vector이다. can_go vector는 정말 갈 수 있는 node들만 넣은 것이고, candidates[i]가 true이고 해당 node를 추가함으로써 늑대 숫자가 양 숫자보다 크거나 같아지면 탐색 불가능이므로 그렇지 않을 때만 node를 넣는다.

이후에는 can_go 내의 node들로 DFS를 한다. DFS 할 때에는 node를 사용했으므로 candidate[node]를 false로 두고 node의 child들을 true로 만들어 준다.

// 양과 늑대

#include <string>
#include <iostream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

vector<int> parent(17, -1); // parnet[i] : i의 parent node
vector<vector<int>> child(17);
vector<int> infos;
int answer = -1;

// candidates : 후보
void DFS(int cur_node, int num_sheep, int num_wolf, vector<bool> candidates){
    vector<int> can_go; // 탐색 가능한 노드들
    int diff = num_sheep - num_wolf;
    for(int i = 0; i<candidates.size(); i++){
        if(candidates[i] == false) continue;
        if(diff - infos[i] > 0) can_go.push_back(i);
    }
    
    if(can_go.size() == 0){ // 종료 조건
        answer = max(answer, num_sheep);
        return;
    }
    
    for(int node : can_go){ // 탐색 가능한 노드들로 DFS
        candidates[node] = false;
        for(int c : child[node]){
            candidates[c] = true;
        }
        
        if(infos[node] == 0) DFS(node, num_sheep+1, num_wolf, candidates);
        else DFS(node, num_sheep, num_wolf + 1, candidates);
        
        candidates[node] = true;
        for(int c : child[node]){
            candidates[c] = false;
        }
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    int num_node = info.size();
    infos = info;
    for(vector<int> edge : edges){
        parent[edge[1]] = edge[0];
        child[edge[0]].push_back(edge[1]);
    }
    
    vector<bool> candidates(num_node, false);
    for(int c : child[0]){
        candidates[c] = true;
    }
    DFS(0, 1, 0, candidates);
    
    
    

    
    return answer;
}