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

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

조건에 따라 가장 많은 양을 데리고 올 수 있는 경우를 구하는 문제

- 단방향 그래프 // 노드 개수 - 1 = 간선 수

- 이동할 수 있는 노드에 대해서 DFS 알고리즘을 적용

DFS) BackTracking

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

풀이 코드

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

public class Solution
{
    public void DFS(ref int[] info, ref int[,] edges, ref bool[] boolArray
                    , ref int answer, int sheepCount, int wolfCount)
    {
        if(sheepCount <= wolfCount)
            return;
        
        answer = Math.Max(answer, sheepCount);
        
        for(int i = 0; i < edges.GetLength(0); i++)
        {
            int parentNode = edges[i, 0];
            int childNode = edges[i, 1];
            
            if(boolArray[parentNode] && !boolArray[childNode])
            {
                boolArray[childNode] = true;
                
                if(info[childNode] == 1)
                    DFS(ref info, ref edges, ref boolArray, ref answer, sheepCount, wolfCount + 1);
                else
                    DFS(ref info, ref edges, ref boolArray, ref answer, sheepCount + 1, wolfCount);
                
                boolArray[childNode] = false;
            }
        }
    }
    
    public int solution(int[] info, int[,] edges)
    {
        int answer = 0;
        bool[] boolArray = new bool[info.Length];
        boolArray[0] = true;
        DFS(ref info, ref edges, ref boolArray, ref answer, 1, 0);
        
        return answer;
    }
}