[프로그래머스] 양과 늑대 (2022 KAKAO Blind Recruitment) : Cpp

 

프로그래머스 양과늑대

문제

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

 

알고리즘 아이디어

1. 모든 노드를 탐색해야 한다.

2. 탐색을 할 때, 갈 수 있는 모든 자리를 다 들고 다녀야 한다... 그럼 너비탐색이 맞지 않나 싶지만 코드가 너무 어지럽다...

 

따라서 DFS에서 Queue를 같이 들고 다니는 이상한 알고리즘이 탄생한다.

 

코드

#include <string>
#include <queue>
#include <vector>

using namespace std;

vector<vector<int>> graph;
int maxSheep = 0;

void DFS(int wolf, int sheep, int nowNode, vector<int> info, queue<int> q) {
    if(info[nowNode] == 0) {
        sheep++;
    } else {
        wolf++;
    }
    
    if (wolf >= sheep) {
        return;
    }
    if (maxSheep < sheep) {
        maxSheep = sheep;
    }
    
    for(int x = 0; x < graph[nowNode].size(); x++) {
        q.push(graph[nowNode][x]);
    }
    
    
    for(int x = 0; x < q.size(); x++) {
        int nextNode = q.front();
        q.pop();
        DFS(wolf, sheep, nextNode, info, q);
        q.push(nextNode);
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    graph.resize(info.size(), vector<int>());
    
    for(int i = 0; i < edges.size(); i++) {
        int nowNode = edges[i][0];
        int nextNode = edges[i][1];
        
        graph[nowNode].push_back(nextNode);
    }
    queue<int> q;
    
    DFS(0,0,0,info, q);
    
    return maxSheep;
}

 

참고문헌

양과늑대 알고리즘 구현