[프로그래머스][C++] 양과 늑대

양과 늑대

문제 링크

양과 늑대

분석

각 노드는 양이나 늑대를 나타냅니다.
양은 0, 늑대는 1입니다.

루트 노드에서 시작하여 트리를 탐색합니다.
이때 루트 노드는 0번입니다.

탐색 중 양의 수가 늑대의 수보다 많아야합니다.
그렇지 않은 경우는 유효하지 않은 경우입니다.

이동 가능한 노드는 현재 위치에서 직접 연결된 자식 노드와 이전에 방문했던 노드의 자식 노드들이 포함됩니다.

위의 조건을 만족하면서 모을 수 있는 양의 최대값을 구해야합니다.

완전탐색, DFS, BFS를 통해 탐색할 수 있습니다.

트리 구조이지만, 문제의 조건이 이전에 방문한 노드의 자식 노드도 다시 방문할 수 있으므로, 단순한 트리 탐색이 아닌 그래프 탐색의 관점으로 접근해야합니다.

양과 늑대의 수를 추적하여 조건을 만족하는 경로만 탐색해주어야합니다.

풀이

#include <vector>
#include <algorithm>
#include <set>

using namespace std;

// 최대로 모은 양의 수를 저장
int answer = 0;

// 트리 형태의 그래프를 저장할 벡터
vector<vector<int>> graph;

// info : 각 노드(동물)의 정보 0 = 양, 1 = 늑대
// currentNode : 현재 방문 중인 노드
// sheep : 현재까지 모은 양의 수
// wolf : 현재까지 모은 늑대의 수
// nextNodes : 앞으로 방문 가능한 노드 집합
void dfs(const vector<int>& info, int currentNode, int sheep, int wolf, set<int> nextNodes)
{
    // 현재 노드에 따라 양이나 늑대의 수를 증가
    if (info[currentNode] == 0)
    {
        ++sheep;
    }
    else
    {
        ++wolf;
    }
    
    // 양의 수가 늑대 수 이하가 되는 경우 유효하지 않으므로 중단
    if (sheep <= wolf)
    {
        return;
    }
    
    // 최대 양 수를 갱신
    answer = max(answer, sheep);
    
    // 현재 노드는 방문했으므로 다음 후보 노드에서 제거
    nextNodes.erase(currentNode);

    // 현재 노드의 자식 노드들을 다음 후보 노드에 추가
    for (int child : graph[currentNode])
    {
        nextNodes.insert(child);
    }
    
    // 다음 방문 가능한 모든 노드들에 대해서 DFS 재귀 호출
    for (int next : nextNodes)
    {
        dfs(info, next, sheep, wolf, nextNodes);
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    // 노드 수만큼 빈 벡터 생성
    graph.resize(info.size());
    
    // 간선 정보를 바탕으로 그래프 구성
    for (auto edge : edges)
    {
        graph[edge[0]].push_back(edge[1]);
    }
    
    // 루트 노드를 후보 노드로 설정 후 dfs 탐색 시작
    set<int> nextNodes = {0};
    dfs(info, 0, 0, 0, nextNodes);
    
    return answer;
}

성능 요약

시간 복잡도는 $O(2^n)$입니다.

• 그래프를 구성하는 반복문 $O(n)$
• DFS 탐색 $O(2^n)$
• $O(n) + O(2^n)$

공간 복잡도는 $O(n)$입니다.

• 그래프를 저장하는 벡터 vector<vector<int>> graph $O(n)$
• DFS 재귀 호출 스택 $O(n)$
• 앞으로 방문 가능한 노드 집합 set<int> nextNodes $O(n)$
• $O(n) + O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 3.63MB)
테스트 2 〉 통과 (0.03ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 3.58MB)
테스트 4 〉 통과 (0.01ms, 3.61MB)
테스트 5 〉 통과 (0.05ms, 4.18MB)
테스트 6 〉 통과 (0.05ms, 3.66MB)
테스트 7 〉 통과 (0.02ms, 4.15MB)
테스트 8 〉 통과 (0.02ms, 4.2MB)
테스트 9 〉 통과 (0.12ms, 4.2MB)
테스트 10 〉 통과 (0.74ms, 4.16MB)
테스트 11 〉 통과 (0.05ms, 3.64MB)
테스트 12 〉 통과 (0.31ms, 4.15MB)
테스트 13 〉 통과 (0.02ms, 4.15MB)
테스트 14 〉 통과 (0.02ms, 4MB)
테스트 15 〉 통과 (0.09ms, 4.2MB)
테스트 16 〉 통과 (0.14ms, 4.2MB)
테스트 17 〉 통과 (2.22ms, 4.01MB)
테스트 18 〉 통과 (0.14ms, 4.15MB)