[알고리즘/C#] 프로그래머스 - 양과 늑대 (Lv.3, DFS? 완전탐색?)

🎈 풀이 방법
처음에 대충 훑어봤을 때는 평범한 DFS 문제라고 생각했다.
그러나 한번 방문했던 노드를 다시 방문할수 있다는 함정이 숨어있었다..
그래서 노드 클래스를 만들고, 트리 구조로 해결하려고 했는데..
굳이 그럴 필요가 없을 것 같아서 모두 날리고 간선 배열을 재귀로 탐색하도록 했다.

using System;
using System.Collections.Generic;

public class Solution {
    List<bool> visited = new List<bool>();
    int maxSheepCnt = 0;

    public void DFS(ref int[,] edges, ref int[] info, int sCnt, int wCnt)
    {
        if (wCnt >= sCnt)    return;

        maxSheepCnt = Math.Max(maxSheepCnt, sCnt);

        for (int i = 0; i < edges.GetLength(0); ++i)
        {
            int parent = edges[i, 0];
            int child = edges[i, 1];
			
            // ▶ 부모 노드를 방문한적이 있어야 자식 노드 방문 가능
            // ▶ 다시 말해, 부모 노드를 방문한적이 있으면 자식 노드 언제든 방문 가능
            // ▶ 문제의 예시와 같이 여기저기 왔다갔다 하면서 양 콜렉 가능
            if (visited[parent] && visited[child] == false)
            {
                visited[child] = true;
                DFS(ref edges, ref info, sCnt + ((info[child] == 0) ? 1 : 0), wCnt + ((info[child] == 1) ? 1 : 0));
                visited[child] = false;
            }
        } 
    }

    public int solution(int[] info, int[,] edges)
    {
        int sheepCnt = 0;
        int wolfCnt = 0;

        for (int i = 0; i < info.Length; ++i)
            visited.Add(false);

        visited[0] = true;
        sheepCnt = 1;

        DFS(ref edges, ref info, sheepCnt, wolfCnt);

        return maxSheepCnt;
    }
}