(C#) 등대

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

프로그래머스

 

풀이

0. n번 등대에 불이 켜져있는지 기록하는 배열 lighten을 준비한다

1. 주어진 간선리스트를 인접리스트로 변환

2. foo함수 실행

3. lighten에서 불이 켜져있는 등대의 갯수를 센다

 

void foo(int current, List<int>[] graph, bool[] lighten, int parent) 함수는 current노드에 불을 켤지 말지를 정하는 함수이다.

foo함수의 진행과정은

1. 먼저 current노드의 자식들에 대해서 foo를 재귀한다.

2. 자식 노드들 중에 불을 켠 노드가 있는지 확인한다.

2-1. 만약 불을 켠 노드가 있다면 그대로 함수를 종료한다.

2-2. 만약 불을 켠 노드가 없다면 current 노드에 불을 켠다.

 

이 foo 함수를 실제로 돌려보면 lighten에 노드들이 켜져있는지 아닌지가 표시된다.

위 그림은 문제에 예시로 들어있는 그림이다.

 

foo함수가 정상적으로 작동하려면 위 그림처럼 1, 5번 노드에 불이 켜져야한다.

그런데 실제로 foo함수를 돌려보면 반대로 1, 5번 노드에만 불이 안들어온다.

이 문제를 해결하기보다는 그냥 전체 등대의 갯수 n에서 foo를 한 결과를 빼기로 했다.

코드

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int n, int[,] lighthouse)
    {
        int answer = 0;
        // 인접 리스트로 변환
        var graph = new List<int>[n + 1];
        for (var i = 0; i < lighthouse.GetLength(0); i++)
        {
            if (graph[lighthouse[i, 0]] == null)
            {
                graph[lighthouse[i, 0]] = new List<int>();
            }
            if (graph[lighthouse[i, 1]] == null)
            {
                graph[lighthouse[i, 1]] = new List<int>();
            }
            graph[lighthouse[i, 0]].Add(lighthouse[i, 1]);
            graph[lighthouse[i, 1]].Add(lighthouse[i, 0]);
        }

        bool[] lighten = new bool[n + 1];

        foo(1, graph, lighten, -1);

        for (var i = 0; i < lighten.Length; i++)
        {
            if (lighten[i]) answer++;
        }

        return n - answer;
    }

    // 어떤 노드의 자식 노드가 모두 꺼져있으면 불을 켜는 함수
    void foo(int current, List<int>[] graph, bool[] lighten, int parent)
    {
        // 자식들에 대해서 재귀
        foreach (var child in graph[current])
        {
            if (child != parent)
                foo(child, graph, lighten, current);
        }
        // 자식들 중에 불을 켠게 있는지 확인
        foreach (var child in graph[current])
        {
            if (child != parent && lighten[child])
                return;
        }
        lighten[current] = true;
    }
}