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

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

프로그래머스

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

주어진 조건에 따라 가장 많은 양을 데리고 올 수 있는 경우를 구하는 문제- 주어진 조건의 노드의 최대 개수가 17개이며, 단방향 그래프로 간선의 수는 16개 ( 노드의 개수 - 1 )

- 현재  탐색 중인 노드만을 기준으로 하는 것이 아닌, 갈 수 있는 노드를 탐색 대상으로 둬야 함

 -> 방문 배열을 선언하여 모든 간선에 대해 부모 노드는 방문하였고, 자식 노드는 방문하지 않았다면 갈 수 있는 노드이므로 탐색 대상으로 둠

 

DFS) BackTracking

https://godgjwnsgur7.tistory.com/47

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

 

주석 참조

    using System;

    public class Solution
    {
        public int solution(int[] info, int[,] edges)
        {
            int answer = 0;
            var boolArray = new bool[info.Length]; // 방문배열
            
            // 초기 값 세팅
            boolArray[0] = true;
            
            // DFS 탐색 ( 초기 값은 최상위 노드를 탐색한 상태로 시작 )
            DFS(1, 0, boolArray, info, edges, ref answer);

            return answer;
        }

        public void DFS(int sheepCount, int wolfCount, bool[] boolArray, int[] info, int[,] edges, ref int answer)
        {
            // Back Tracking 조건 (양이 잡아먹힘)
            if (sheepCount <= wolfCount)
                return;

            // 최대 값이라면 갱신
            answer = Math.Max(answer, sheepCount);

            // 모든 노드를 순회하여 갈 수 있는 노드를 찾음
            for (int i = 0; i < edges.GetLength(0); i++)
            {
                int parentIndex = edges[i, 0];
                int childIndex = edges[i, 1];

                // 현재 갈 수 있는 노드인 경우
                if (boolArray[parentIndex] && !boolArray[childIndex])
                {
                    boolArray[childIndex] = true;

                    if (info[childIndex] == 0)
                        DFS(sheepCount + 1, wolfCount, boolArray, info, edges, ref answer);
                    else
                        DFS(sheepCount, wolfCount + 1, boolArray, info, edges, ref answer);

                    boolArray[childIndex] = false;
                }
            }
        }
    }