양과 늑대
문제 링크 : 양과 늑대
문제 설명
2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.
예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.
각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 2 ≤ info의 길이 ≤ 17
- info의 원소는 0 또는 1 입니다.
- info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
- 0은 양, 1은 늑대를 의미합니다.
- info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
- edges의 세로(행) 길이 = info의 길이 - 1
- edges의 가로(열) 길이 = 2
- edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
- 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
- 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
- 0번 노드는 항상 루트 노드입니다.
입출력 예
| info | edges | result |
|---|---|---|
| [0,0,1,1,1,0,1,0,1,0,1,1] | [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] | 5 |
| [0,1,0,1,1,0,1,0,0,1,0] | [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] | 5 |
풀이 방법
- 먼저 info의 최대 길이가 17인 것을 보아서 각 노드들을 선택할지 말지 완전탐색을 통해서
O(2^N)으로 풀어도 될 것으로 보여, 해당 풀이 방법으로 풀고자 했다. - 각 노드들을 선택하는 기준을 정하는데, 간선에 따라 방문할 수 있는 노드가 달라지기 때문에 먼저 edges를 인접 리스트로 만들었고, 이를 이용해서 현재 노드를 통해 선택할 수 있는 노드를 개방하는 식으로 구현했다.
- 양 노드에 도달했을 때는 양의 개수를 늘려주고, 최대 값과 비교를 했다. 늑대 노드에 도달했으면 양과 비교해서 같거나 크면 양의 개수를 0으로 하고 return을 통해 해당 노드 흐름을 종료했다. 크거나 같아서 양이 0마리가 되면 앞으로 들어오는 양은 모두 제거되기 때문이다.
- dfs 방식을 통해서 구현했기 때문에, 방문여부와 방문 가능 여부를 체크한 후에 재귀를 통해 모든 노드를 검사하는 방식을 통해 문제를 해결했다.
-> 해당 문제 풀이는O(2^N)의 시간복잡도를 가지나, 특정 조건에서는 가지치기를 하기 때문에 더 작은 시간이 소요될 것으로 추측되고, 알맞은 알고리즘으로 보인다.
구현
#include <string>
#include <vector>
using namespace std;
int maxSheep = 0;
// 각 노드들을 선택할지 말지 (2^n) - dfs
void search(int i, int count, int n, int sheep, int wolf, vector<bool> visited, vector<bool> canVisit,
vector<int>& info, vector<vector<int>>& graph){
if(count >= n){
return;
}
visited[i] = true;
// 양 노드
if(info[i] == 0){
sheep += 1;
maxSheep = max(maxSheep, sheep);
}else{ // 늑대 노드 (늑대가 같아지면 무조건 양이 0마리가 될 수 밖에 없음)
wolf += 1;
if(sheep <= wolf){
sheep = 0;
return;
}
}
// 현재 노드를 통해 선택할 수 있는 노드 개방
for(int k : graph[i]){
canVisit[k] = true;
}
// 선택할 수 있는 노드 모두 순회
for(int k = 0; k < n; k++){
if(canVisit[k] && !visited[k]){
search(k, count + 1, n, sheep, wolf, visited, canVisit, info, graph);
}
}
}
int solution(vector<int> info, vector<vector<int>> edges) {
int n = info.size();
vector<vector<int>> graph(n);
vector<bool> visited(n, false);
vector<bool> canVisit(n, false);
canVisit[0] = true;
for(vector<int>& edge : edges){
graph[edge[0]].push_back(edge[1]);
}
search(0, 0, n, 0, 0, visited, canVisit, info, graph);
int answer = maxSheep;
return answer;
}