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

문제

lv3 양과 늑대 문제 링크

아래 그림과 같이 양과 늑대가 주어진다. 0에서 시작해서 지나가는 노드의 양과 늑대를 모은다. 늑대>=양 이면 양이 모두 잡아먹힌다. 양이 잡아먹히지 않으면서 모을 수 있는 양의 최댓값을 구한다.
주의할 점은 지나왔던 노드를 재방문할 수 있다는 점이다. 예를 들어 0 -> 1 로 이동해 현재 1 위치에 있다면 그 다음 방문할 수 있는 노드는 [2, 4, 8]이 된다.

풀이

{ 현재 인덱스, 다음 단계에 방문할 수 있는 노드 목록, 양의 수, 늑대 수 }를 담아서 dfs로 탐색한다.
각 탐색마다 양의 수를 최댓값으로 갱신하고, 늑대>=양 이면 리턴한다. 위에 있는 그림대로 입력이 주어졌을 때의 탐색 과정은 대략 다음과 같다. (까먹고 표시하지 않았는데 형광펜 친 부분 아래로도 계속 탐색이 이어진다)

다음 단계에 방문할 수 있는 노드 목록을 전달하지 않고 단순히 현재 인덱스와 연결된 노드를 방문하면 1과 8은 연결되어 있지 않으므로 0 -> 1 -> 8과 같은 이동이 안된다.

소스코드

#include <string>
#include <vector>

using namespace std;

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

void navigate(vector<int> info, int idx, vector<int> nextN, int sheep, int wolf) {
    int s = sheep;
    int w = wolf;
    if (info[idx] == 0) s++;
    else w++;
    answer = max(answer, s);
    if (s <= w) return;

    for (int i = 0; i < nextN.size(); i++) {
        vector<int> tmp = nextN;
        tmp.erase(tmp.begin() + i);
        for (auto j: graph[nextN[i]]) tmp.push_back(j);
        navigate(info, nextN[i], tmp, s, w);
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {

    int n = info.size();
    graph.assign(n, vector<int>());

    for (auto i: edges) {
        graph[i[0]].push_back(i[1]);
    }
    vector<int> nextN;
    for (auto i: graph[0]) {
        nextN.push_back(i); // 0과 연결된 노드 담기
    }

    navigate(info, 0, nextN, 0, 0);

    return answer;
}

---

DFS, BFS 그래프 탐색은 이제 자신있다고 생각했는데 조금만 변형되면 여전히 어렵다...