<Lv.3> 양과 늑대 (프로그래머스 : C#)

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

📕 문제 설명

2진 트리 모양의 각 노드에 늑대와 양이 한 마리씩 놓인다. 루트 노드에서 출발해 양을 모은다. 각 노드를 방문할 때 마다 해당 노드의 양과 늑대가 따라오게 되는데 다음의 경우 늑대가 모든 양을 잡아먹는다. (모은 양의 수 <= 늑대의 수)

최대한 많은 수의 양을 모아 루트 노드로 돌아올 때 최대 모을 수 있는 양의 수 반환하기

• Input
  각 노드의 양 또는 늑대 정보 info, 노드 연결 관계 edges
• Output
  최대한 모을 수 있는 양의 수

예제

풀이

현재 sheep count를 기준으로 트리에서 타고 갈 수 있는 부분들에 대해 재귀로 타고 들어가며 가능한 양의 개수들을 센다. (부모 방문 o, 자식 방문 x 케이스) => 현재 노드에서 자식들을 볼 수 있고 위에 타고 오면서 이전에는 늑대 개수로 인해 방문하지 못했던 노드들에 대해 양의 개수가 업데이트 된 상태에서 다시 방문해볼 수 있도록 하기 위해 해당 조건 사용

🔸 point 1. 기존 dfs 문제들의 경우 visited 배열로 주로 끝나는 조건을 파악하는데 이 문제에서 재귀를 끝내는 조건은 wolf가 많아지는 순간 더 이상 탐색을 할 필요가 없다는 점을 파악해야 한다.

🔸 point 2. 흔히 보는 dfs문제들은 currNode 값을 넘겨서 인접 노드들 순회하면서 가능한 조건에 부합할 때 dfs를 진행하는데 모든 edges에 대해 매 재귀마다 확인하는 방식으로 진행한다. 특정 child 노드에 방문하며 양의 개수가 변하는데 변한 양의 개수를 기반으로 위의 다른 노드들에 방문하는 케이스도 봐야하기 때문이다.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    bool[] visited;
    int[,] edges;
    int[] info;
    HashSet<int> sheepCounts;
    public int solution(int[] info, int[,] edges) {
        this.info = info;
        this.edges = edges;
        sheepCounts = new HashSet<int>();
        visited = new bool[info.Length];
        
        visited[0] = true;
        DFS(1, 0);
        
        return sheepCounts.Max();
    }
    
    private void DFS(int sheep, int wolf)
    {  
        if (wolf >= sheep) return; // wolf가 많아지는 경우 그 뒤 sheep 만나면 무조건 먹히므로 pass
        sheepCounts.Add(sheep); // 현재 sheep count 저장
        
        for (int i = 0; i < edges.GetLength(0); i++)
        {
            int parent = edges[i, 0];
            int child = edges[i, 1];
            int wolfCount = info[child];
            // 부모 방문하고 아직 자식 방문 안한 경우에 대한 케이스 모두 확인
            if (visited[parent] && visited[child] == false)
            {
                visited[child] = true;
                DFS(sheep + 1 - wolfCount, wolf + wolfCount); // dfs로 돈 다음
                visited[child] = false; // 방문 표시 빼기 
            }
        }
        
    }
}

결과