[프로그래머스 Programmers] 양과 늑대 (풀이 진행중)

문제 설명

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

 

프로그래머스

 

 

풀이 코드 (실패한 풀이 코드)

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

namespace backjun
{
    public class Graph
    {
        private int m_sheepCount;
        private int m_wolfCount;
        private int[] m_infos;
        private int[,] m_infoEdges;
        private bool[] m_visited;
        private Queue<(int, int, int)> m_root;

        public Graph(int[] infos, int[,] infoEdges)
        {
            m_sheepCount = 1;
            m_wolfCount = 0;
            m_infos = infos;
            m_infoEdges = infoEdges;
            m_visited = new bool[infos.Length];
            m_root = new Queue<(int, int, int)>();
        }

        public void AddEdge(int src, int dst, int priority)
        {
            m_root.Enqueue((src, dst, priority));
        }

        public void BFS()
        {
            m_visited[0] = true;

            while (m_root.Count > 0)
            {
                var maxValue = m_root.Max(a => a.Item3);

                var item = m_root.Dequeue();
                if (item.Item3 == maxValue)
                {
                    if (!m_visited[item.Item2])
                    {
                        m_visited[item.Item2] = true;

                        for (int i = 0; i < m_infoEdges.GetLength(0); i++)
                        {
                            var temp = m_infoEdges[i, 0];
                            if (temp == item.Item2)
                            {
                                m_root.Enqueue((m_infoEdges[i, 0], m_infoEdges[i, 1], m_infos[i]));
                            }
                        }
                    }

                    var animal = m_infos[item.Item2];
                    if (animal == 1)
                    {
                        if (m_sheepCount == m_wolfCount)
                        {
                            if (m_root.Count == 1)
                            {
                                break;
                            }

                            m_root.Enqueue(item);
                            continue;
                        }

                        m_wolfCount++;
                    }
                    else
                    {
                        m_sheepCount++;
                    }

                    Console.WriteLine($"root {item.Item1} -> {item.Item2}, sheep : {m_sheepCount}, wolf : {m_wolfCount}");
                }
                else
                {
                    m_root.Enqueue(item);
                }
            }
        }
    }

    public class Program
    {
        static void Main(string[] args)
        {
            int[] info = { 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1 };
            int[,] inputEdges = {
                { 0, 1 },
                { 1, 2 },
                { 1, 4 },
                { 0, 8 },
                { 8, 7 },
                { 9, 10 },
                { 9, 11 },
                { 4, 3 },
                { 6, 5 },
                { 4, 6 },
                { 8, 9 } };

            Graph g = new Graph(info, inputEdges);

            for (int i = 0; i < inputEdges.GetLength(0); i++)
            {
                if (inputEdges[i, 0] == 0)
                {
                    g.AddEdge(inputEdges[i, 0], inputEdges[i, 1], info[i]);
                }
            }

            g.BFS();
        }
    }
}