[C++] Programmers Lv. 3 "양과 늑대"

🔵 문제 링크

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

프로그래머스

 

💡 Point

모든 경우의 수를 찾는다. (백트래킹)

문제에서 제시된 것처럼 한 노드를 방문했더라도, 그 노드를 다시 방문할 수 있다는 것을 주의해야 한다.

 

나는 처음에 여태 풀어왔던 그래프 탐색 문제 풀이처럼 하나씩 탐색하는 방식으로 접근해서 틀렸었다.

이 문제에서 중요한 것은!

방문 가능한 노드들을 모아놓는 것이다.

지금 방문했을 때, 조건이 안 되어 (늑대 수 >= 양 수) 더 진행할 수 없더라도, 다른 노드를 탐색하고 다시 왔을 때는 조건을 만족하여 새로운 경우의 수를 찾을 수 있기 때문이다. 

 

set을 사용하여 방문 가능한 노드들의 인덱스를 저장하였다.

어떤 한 노드를 방문하게 되면, 그 노드의 자식들도 방문할 수 있게 되므로 set에 저장한다.

(무한 재귀를 방지하기 위해 자신은 삭제한다.)

 

🔵 전체 코드

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

using namespace std;

unordered_map<int, vector<int>> tree;
int ans;

// 최대한 많은 양을 찾는다.
// 방문했던 노드는 다시 방문할 수 있다!!
// 방문했던 노드의 자식들도 그냥 바로 방문할 수 있다.
// 방문 가능한 노드들을 모아서 넘겨준다.!!!!! 
void dfs(vector<int>& info, set<int> visits, int node, int sheep, int wolf)
{
    sheep += (info[node] == 0 ? 1 : 0);
    wolf += (info[node] == 1 ? 1 : 0);

    if (sheep <= wolf)
        return;

    // 양 최대 마릿수 구하기
    ans = max(ans, sheep);

    // 자기 자신 호출 방지
    visits.erase(node);

    // 자식 노드들을 방문할 수 있는 노드 집합에 저장
    for (int child : tree[node])
        visits.insert(child);

    // 방문 가능한 노드 전체를 순회
    for (int next : visits)
        dfs(info, visits, next, sheep, wolf);
}

// 0은 양, 1은 늑대를 의미합니다.
// 모든 경우의 수를 찾는다. DP (노드 최대 개수는 17으로 매우 작음.)
int solution(vector<int> info, vector<vector<int>> edges) 
{
    for (vector<int> edge : edges)
    {
        int parent = edge[0];
        int child = edge[1];

        tree[parent].push_back(child);
    }

    set<int> visits;
    for (int child : tree[0])
        visits.insert(child);

    dfs(info, visits, 0, 0, 0);

    return ans;
}

 

🔵 시간 복잡도

n이 노드의 개수일 때, 시간 복잡도는 최악의 경우 O(2^n)이다.

하지만 문제에서 n은 최대 17이므로 걱정 안 해도 된다.