양과 늑대 92343

문제

접근 방법

처음에는 각각의 양까지 만나는 늑대의 수만 기록하고 낮은 순대로 차례대로 합해가면 되지 않을까 싶었다.

하지만 문제가 있었다. 각각 2개의 늑대를 지나치면 되지만 실제로는 3개의 늑대를 지나쳐야 2개 다 가질 수 있던 것이다.

생각하다 보니 '막히면 다른 곳으로 가는 건 어떨까?'라는 생각이 들었다. 갈 수 있는 경로를 저장하고 가는 것이다.

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;
int ret = 0;
vector<vector<int>> map;
void dfs(int idx, int sheep, int wolf, vector<int> &info, queue<int> path)
{
    if (info[idx])
        ++wolf;
    else
    {
        ++sheep;
        ret = (ret > sheep) ? ret : sheep;
    }
    if (wolf >= sheep)
        return;
    for (int m : map[idx])
        path.push(m);
    for (int i = 0; i < path.size(); ++i)
    {
        int next = path.front();
        path.pop();
        dfs(next, sheep, wolf, info, path);
        path.push(next);
    }
}
int solution(vector<int> info, vector<vector<int>> edges)
{
    map = vector<vector<int>>(info.size(), vector<int>());
    for (auto edge : edges)
    {
        map[edge[0]].push_back(edge[1]);
    }
    dfs(0, 0, 0, info, {});
    return ret;
}

풀이

원래 vector로 풀려 했는데 삭제하고 다시 추가하는 과정이 매끄럽지 못할 것 같아서 큐로 작성했다. 이동할 수 있는 모든 경로를 추가해주고 현재 가는 경로를 제거해주는 방식으로 DFS를 돌면 된다.