[Algorithm] DFS 프로그래머스 92343번 양과 늑대 | C++

※ 2022 KAKAO BLIND RECRUIMENT : 양과 늑대

코딩테스트 연습 - 양과 늑대 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

2022.09.01 - [c++/DFS&BFS] - [Algorithm] DFS(Depth-First Search,깊이 우선 탐색) 프로그래머스 92342

[Algorithm] DFS(Depth-First Search,깊이 우선 탐색) 프로그래머스 92342

문제 해결 TIP

• 트리를 탐색하면서 최대 양의 마릿수를 구하는 문제
• 트리 탐색 순서가 중요해 보이지만, 실상은 중요하지 않다. 방문했던 노드와 바로 인접한 노드라면 모두 접근이 가능하므로, 해당 문제는 경로는 생각하지 않고, 다음에 방문 가능한 노드가 무엇인지만 파악하고 있으면 된다.

문제 해결 풀이

1. [부모노드, 자식노드] 형태로 서로 연결된 두 노드를 담고있는 2차원 배열 edges가 있다. 해당 배열 사이즈만큼 순회하면서 인접 리스트를 구성한다.(트리 구현을 위해 필요)
2. 다음에 방문 가능한 노드를 담는 배열인 nextNode를 선언하고, 루트노드에서 방문가능한 노드들을 우선적으로 nextNode에 담는다.
3. 현재 노드에 있는 동물이 늑대인지 양인지 확인 후, 해당 동물의 count를 +1 해준다.
4. 기존 양의 최댓값을 확인 후 더 크다면 갱신해준다
5. 만약 현재 노드에 방문함으로서 늑대와 양의 수가 같거나, 늑대가 더 많아졌다면 잡아먹히기 때문에 return한다.
6. 그렇지 않은 경우에는, nextNode속 방문 가능한 노드를 순차적으로 방문한다. - 방문하기에 앞서, 다음으로 방문할 노드는 nextNode 배열에서 지우고, 다음으로 방문할 노드에서 방문가능한 노드들을 nextNode배열에 추가한다.
7. 순회하면서 구한 최대값을 리턴하고, 출력한다.

---

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int dfs(int currIdx, int wolf, int sheep, vector<int> nextNode, vector<int> info, vector<vector<int>> &adjList, int answer) {
		int isWolf = info[currIdx];
    if(!isWolf) sheep++;
    else wolf++;
    
	  //현재 양 마릿수와 최대 양 마릿수를 비교하여 최대값으로 정답을 갱신
    answer = max(answer, sheep);
    
	  //늑대수가 양의 수보다 같거나 많아졌다면 return
    if(wolf >= sheep) return answer;
    
		//현재 방문가능한 노드들을 순차적으로 방문
    for(int i = 0; i < nextNode.size(); i++) {
        vector<int> next = nextNode;
        next.erase(next.begin()+i); //다음으로 방문할 노드는 배열에서 삭제 후 재귀 파라미터에 전달
        
        for(int j = 0; j < adjList[nextNode[i]].size(); j++) {
            next.push_back(adjList[nextNode[i]][j]); 
        }
        answer = dfs(nextNode[i], wolf, sheep, next, info, adjList, answer);
    }
    return answer; //현재 방문가능한 노드들을 모두 방문했으면 return
}

int solution(vector<int> info, vector<vector<int>> edges) {
   vector<vector<int>> adjList(info.size());
    int answer = 1;

    for(int i = 0; i < edges.size(); i++) {
        adjList[edges[i][0]].push_back(edges[i][1]);
    }
    
    vector<int> nextNode; 
    for(int i = 0; i < adjList[0].size(); i++) {
        nextNode.push_back(adjList[0][i]);
    }
    
    answer = dfs(0, 0, 0, nextNode, info, adjList, answer); 
    
    return answer;
}