[프로그래머스 C#] Lv.3 등대

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

프로그래머스

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

조건을 만족시키는 켜진 등대의 총 개수의 최소 값을 구하는 문제

- 등대를 노드(정점), 등대 간의 연결상태를 간선으로 둠

- 연결된 두 노드 중 하나는 무조건 켜져있어야 함

 

- 간선의 개수는 정점의 개수 - 1개, 모든 등대는 서로 연결된 길에 따라 서로 이동할 수 있음

 -> 사이클을 이룰 수 없음 ( ex. a -> b, b -> c, c -> a )

 

- 최소 개수를 구하기 위해서는 초기에 존재하는 모든 리프노드는 불이 들어와선 안됨

 -> 초기 리프노드와 연결된 노드는 무조건 불이 켜져야 함

 

풀이 방법 (BFS 알고리즘)

리프 노드를 최하위 노드로 보고, 자식(하위) 노드 -> 부모(상위) 노드 방향으로 탐색

-> 리프 노드에 대한 연산이 끝났다면 재탐색이 필요없으므로 자식 노드와 부모 노드의 연결을 끊어줌 

-> 만약, 현재 탐색 대상인 노드가 리프 노드가 아니라면 연산 중인 다른 자식 노드를 가진 것

 -> 리프 노드가 될 때까지 대기하기 위해 재탐색 대상으로 두고 다음 대상을 체크

 

https://godgjwnsgur7.tistory.com/47

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

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public int solution(int n, int[,] lighthouse)
        {
            int answer = 0;
            var boolArray = new bool[n + 1]; // 등대의 불이 켜져있는지
            var dict = new Dictionary<int, List<int>>(); // 연결된 꺼진 등대
            var queue = new Queue<int>(); // BFS 탐색을 위한 queue

            for (int i = 1; i <= n; i++)
                dict.Add(i, new List<int>());

            // 간선 그래프 세팅
            for (int i = 0; i < lighthouse.GetLength(0); i++)
            {
                dict[lighthouse[i, 0]].Add(lighthouse[i, 1]);
                dict[lighthouse[i, 1]].Add(lighthouse[i, 0]);
            }

            // 초기에 존재하는 모든 리프 노드 번호 세팅
            for (int i = 1; i <= n; i++)
                if (dict[i].Count == 1)
                    queue.Enqueue(i);

            while (queue.Count > 0)
            {
                // 연결된 두 등대 번호 n1, n2
                int n1 = queue.Dequeue();

                // 연결된 등대가 없을 경우
                if (dict[n1].Count == 0)
                    continue;

                // 리프노드가 아닐 경우 재탐색 대상으로 둠
                if (dict[n1].Count != 1)
                {
                    queue.Enqueue(n1);
                    continue;
                }

                // 리프노드라면 탐색을 이어가며 처리
                int n2 = dict[n1][0];

                dict[n1].Remove(n2);
                dict[n2].Remove(n1);

                if (boolArray[n1] == false)
                    boolArray[n2] = true;

                queue.Enqueue(n2);
            }

            // 켜진 등대의 개수 구하기
            foreach (bool b in boolArray)
                if (b) answer++;

            return answer;
        }
    }