프로그래머스[Lv.3] - 양과 늑대

 

 

문제 설명

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번 노드는 항상 루트 노드입니다.

---

 

 

 

 

 

 

풀이

각 노드를 순서대로 방문할 필요는 없고 양과 늑대의 수를 유지해야 하기 때문에 일반적인 DFS나 백트래킹은 아니라고 생각했다.

그래서 방문할 수 있는 노드의 경우를 늘려가는 BFS가 아닐까라는 생각을 했다.

하지만 노드 방문에 대한 기준을 세워 우선순위 큐를 이용하면 될 것이라 생각했다.

내가 세운 기준은 자식 노드의 양의 개수와 현재 노드가 양인지를 기록하는 tuple을 만들어 판단하려 했다.

예를 들어, 두 노드 모두 양이면 자식 노드에 있는 양의 개수가 많은 노드를 선택하는 방식을 사용하려 했다.

하지만, 결과는 절반짜리였다.

 

생각해 보니 바로 밑의 자식만 고려하면 그 이후의 노드들은 판단하기 어려워진다.

그래서 DFS를 이용해 탐색해야 한다고 판단했다.

 

DFS를 통해 한 노드씩 방문하는 것은 맞지만, 현재 노드에서 고를 수 있는 선택지는 BFS처럼 접근 가능한 모든 노드를 고르게 진행하면 된다.

예를 들어, 0번에서 1번 노드와 8번 노드에 접근할 수 있다.

따라서, 접근 가능한 노드를 저장하는 set을 만들고 이에 1, 8을 저장한다.

이후, 1번을 방문했다고 가정하고 1번에서 접근할 수 있는 2, 4번을 추가로 저장하여 {8, 2, 4} 중 하나를 방문하는 방식으로 DFS를 진행하는 것이다.

진행하던 도중 양의 수보다 늑대의 수가 같아지거나 더 많아지면 더 이상 진행할 수 없으므로 최댓값을 갱신하고 종료한다.

또한, 모든 노드를 방문하여 더 이상 방문할 노드가 없을 때도 최댓값을 갱신하고 종료한다.

 

한 가지 주의할 점은 접근 가능 노드들은 어떠한 노드를 방문하는지에 따라 달라지기 때문에 원본을 유지한 채 복사본을 만들어 추가하면서 진행하면 편리하다. 

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <unordered_set>
#include <iostream>

using namespace std;

enum
{
    SHEEP,
    WOLF
};

int answerTemp = 0;

void DFS(vector<vector<int>>& land, vector<int>& info, unordered_set<int>& Connected, int diff, int sheep)
{
    if(diff <= 0)
    {
        answerTemp = max(answerTemp, sheep);
        return;
    }
        
    for(auto next : Connected)
    {
    	//임시 접근 가능 노드
        unordered_set<int> tempSet = Connected;
        tempSet.erase(next);
        for(int temp : land[next]) tempSet.insert(temp);
        
        if(info[next] == SHEEP) DFS(land, info, tempSet, diff+1, sheep+1);
        else DFS(land, info, tempSet, diff-1, sheep);
    }
    
    answerTemp = max(answerTemp, sheep);
}

int solution(vector<int> info, vector<vector<int>> edges) {
    int answer = 1;
    int n = info.size();
    
    vector<vector<int>> land(n+1);
    for(auto& edge : edges) land[edge[0]].push_back(edge[1]);
   
    unordered_set<int> Connected;
    for(int next : land[0]) Connected.insert(next);
    
    DFS(land, info, Connected, 1, 1);
    
    answer = answerTemp;
    return answer;
}

---