[Algorithm] Programmers :: 양과 늑대

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

프로그래머스

vector<vector<int>> graph(18);
int answer;
 
void DFS(int index, int sheepNum, int wolfNum, vector<int> nextNodes, vector<int>& info)
{
    if (info[index] == 0) ++sheepNum;
    else ++wolfNum;
 
    if (wolfNum >= sheepNum) return;
 
    answer = max(answer, sheepNum);
 
    for (int i = 0; i < nextNodes.size(); ++i)
    {
        vector<int> tempNextNodes = nextNodes;
        tempNextNodes.erase(tempNextNodes.begin() + i);
 
        for (int j = 0; j < graph[nextNodes[i]].size(); ++j)
        {
            tempNextNodes.push_back(graph[nextNodes[i]][j]);
        }
 
        DFS(nextNodes[i], sheepNum, wolfNum, tempNextNodes, info);
    }
}
 
 
int solution(vector<int> info, vector<vector<int>> edges) 
{
    answer = 0;
 
    for (int i = 0; i < edges.size(); ++i)
    {
        int a = edges[i][0];
        int b = edges[i][1];
 
        graph[a].push_back(b);
    }
 
    vector<int> nextNodes;
    for (int i = 0; i < graph[0].size(); ++i)
    {
        nextNodes.push_back(graph[0][i]);
    }
 
    DFS(0, 0, 0, nextNodes, info);
 
    return answer;
}
 

완전탐색으로 풀이한 문제입니다.  방문가능한 정점을 (방문한 정점의 자식들)을 계속 갱신하면서 '복사'하는식으로 다음 재귀호출에 넘겨서 탐색하는 방식입니다.

이런식으로 풀어본적은 없어서 쉽게쉽게 풀지는 못했는데, 다음에 비슷한 문제를 풀때는 쉽게 풀 것 같습니다.

 

탐색하다가 막혔을 때(늑대의 수가 양의수 이상일 때), 일단 해당루트로는 탐색을 중지하긴해야하는데 나중에 다시 재탐색을 해야하는것을 어떻게 표현해야하는가?에 대한부분에서 조금 막혔던 것 같습니다.

사실 그렇게 어렵게 생각할것은 없고 그냥 컨테이너에 담아주면 됩니다(벡터든 큐든 뭐든).

그래서 각 정점을 탐색할 때 현재정점을 제외하고, 컨테이너에 현재정점의 자식들을 넣어준 후 그걸 다음 재귀호출에 사용하면 됩니다. 다만, 완전탐색이기 때문에 컨테이너는 복사로 넘겨줘야한다는 걸 명심해야 합니다.