[C#] 등대

프로그래머스 문제

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

풀이 후기

1. 분석

뻔한 DP 문제인데 그리디로 반쯤 구현했을 때 10만으로 돌아갈 리가 없는 것을 깨닫고 억울해서 또 DP로 안 풀었다.

그리고 이 문제 좀 짜증 나는 게 조건이 맘에 안 든다.

한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.

이렇게 일자로 등대가 이어져 있다면, 일반적으로 가운데 등대는 밝혀져 있어서 된다고 착각할 수 있는데 양 등대 중 하나는 켜져 있어야 한다는 조건에 의해 하나는 무조건 켜져 있어야 한다. 근데 다시 생각해보면 상식적으로도 2개 중에 한 개는 켜져 있는 게 맞는 듯... ㅎㅎ;;

아무튼 내가 적용한 방법은 다음과 같다.

어떤 노드가 리프 노드라면, 그 노드와 연결된 다른 노드가 무조건 불을 켜는 것이 이득이다. 다른 노드는 불을 켜고 자신이 연결된 엣지를 모두 잘라버린다. (다른 리프 노드를 생성하기 위해)

1번에 의해 5번은 리프 노드가 되었다. 5번의 요청으로 6번의 엣지를 전부 자른다. 해당 작업을 엣지를 모두 제거할 때까지 반복한다.

이런 느낌으로 알고리즘도 논리도 없이 막 풀었봤는데 아무튼 풀리긴 했다.

2. 실행 결과

3. 코드

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

public class Solution
{
    public static int answer = 0;
    
    public class LightHouse{
        public bool IsLeaf => _edges.Count == 1;
        public bool NeedCheck => 0 < _edges.Count;
        private List<LightHouse> _edges;

        public LightHouse()
        {
            _edges = new List<LightHouse>();
        }

        public void OnLightLeap()
        {
            answer += 1;

            for (var i = 0; i < _edges.Count; i++)
            {
                _edges[i].OnLightDelete(this);
            }
            
            _edges.Clear();
        }
        
        public void OnLightDelete(LightHouse l)
        {
            _edges.Remove(l);
        }

        public void OnLightSend()
        {
            _edges[0].OnLightLeap();
        }

        public void AddNearLight(LightHouse n)
        {
            _edges.Add(n);
        }
    }
    
    public int solution(int n, int[,] lighthouse) {
        var lightHouses = new LightHouse[n + 1];
        var lightHouseQueue = new Queue<LightHouse>();

        for(var i = 1; i < n + 1; i++){
            lightHouses[i] = new LightHouse();
            lightHouseQueue.Enqueue(lightHouses[i]);
        }
        
        for(var i = 0; i < lighthouse.GetLength(0); i++){
            var a = lighthouse[i, 0];
            var b = lighthouse[i, 1];
            lightHouses[a].AddNearLight(lightHouses[b]);
            lightHouses[b].AddNearLight(lightHouses[a]);
        }
        
        while (0 < lightHouseQueue.Count)
        {
            var node = lightHouseQueue.Dequeue();
            if (node.IsLeaf)
            {
                node.OnLightSend();
            }
            else if (node.NeedCheck)
            {
                lightHouseQueue.Enqueue(node);
            }
        }
        
        return answer;
    }
}

새로운 리프 노드를 탐색으로 찾는 것보다는 BFS 느낌으로 연관된 노드를 탐색하는 게 더 좋은 방법이긴 하다. 아마 맨 마지막 노드에서만 계속 리프 노드가 나오면 망할 듯.