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

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

프로그래머스

  DFS로 문제를 푸는 것은, "2 ≤ info의 길이 ≤ 17"을 보고 알 수 있습니다. 또한 그림도 친절하게 트리임을 알 수 있습니다.
하지만 이 문제는 기존 DFS문제를 조금 달랐고, 이렇게 생각해볼 수 있다는 것을 알 수 있었습니다. 해당 글에서는 그런 점에 대해 적어보겠습니다.

 기존 DFS라고 부르고 싶은 로직에서 탐색할 수 있는 노드는 자신에게 연결되어 있는 노드뿐이었습니다. 해당 문제에서 자신에게 연결된 노드가 아니라, 이전 노드, 현재 노드에서 갈 수 있는 곳이었습니다. 또한 이 뿐만 아니라 탐색을 할 수 있는 조건이 탐색하고 있는 중에 상태값이 변경됨에 따라 변경된다는 점도 새로웠습니다. 정리하면 다음과 같습니다.

1. 탐색할 수 있는 곳은 이전 노드와 연결된 노드 + 현재 노드와 연결된 곳
2. 탐색 중에 하위 노드를 탐색할 수 있는 조건이 변경됨 -> 탐색 중에 상태 값이 변경됨

 탐색할 수 있는 노드의 값을 원래 함수에서 들고 다니지 않았지만, 이전 노드와 연결된 곳을 가지고 다녀야 하기때문에 list로 들고 다녀도 되고, set으로 들고 다녀도 된다고 생각이 들었습니다. set으로 들고 다니려고 했는데 이터레이터를 조작하는 것이 너무 복잡해서, 우선 순위 큐로 변경해서 사용하였습니다. 기존 dfs 코드의 틀과 별 다른 점은 없습니다.

 처음 들었던 생각인 다시 올라가서, 다시 어떻게 내려오지엔 막연한 생각이 있었는데 이동할 곳은 저장해서 가지고 다니면 된다는 생각이 새로웠네요.

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
#include <queue>
using namespace std;

int answer = 0;

void dfs(const vector<int> &info, const vector<set<int>> &graph, int node, queue<int> nextNode, int sheep, int wolf) {
    // 현재 노드가 양인지 아닌지 어캐 앎, 양의 최고 개수를 갱신해야함.
if (info[node] == 0) {
        sheep += 1;
    }
    else {
        wolf += 1;
    }
    answer = max(answer, sheep);

    if (sheep <= wolf) {
        return;
    }

    
    // 갈 수 있는 노드를 구해야함.
    for (auto it = graph[node].begin(); it != graph[node].end(); it++) {
        nextNode.push(*it);
    }

    // 순회 돌면서 dfs 내려가기
    // for (auto it = nextNode.begin(); it != nextNode.end();) {
    for(int i=0; i<nextNode.size(); i++) { 
        // 현재 노드는 제거
        int next = nextNode.front();
        nextNode.pop();
        dfs(info, graph, next, nextNode, sheep, wolf);
        nextNode.push(next);
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    vector<set<int>> graph(info.size());
    // 그래프 생성
    for (vector<int> edge : edges) {
        graph[edge[0]].insert(edge[1]);
    }

    dfs(info, graph, 0, { }, 0, 0);

    return answer;
}