<Lv.3> 등대 (프로그래머스 : C#)

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

📕 문제 설명

1~n개의 등대가 존재하고, 등대와 등대 사이를 오가는 뱃길이 n-1개 존재한다. 이때 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있어야 한다. 최소로 켜두어야 하는 등대 개수 반환하기

(즉, 간선마다 연결된 노드 중 하나는 켜져 있어야 한다는 의미)

• Input
  등대 개수, 뱃길 연결 정보
• Output
  켜 두어야 하는 등대 최소 개수

예제

풀이

트리 + 재귀

1) 리프노드
킬 필요 X

2) 리프노드 x
자식 노드들에 대해 재귀를 돌며 해당 노드의 불을 킬 여부를 결정

using System;
using System.Collections.Generic;

public class Solution {
    int answer;
    List<int>[] graph;
    public int solution(int n, int[,] lighthouse) {
        answer = 0;
        // 그래프 초기화
        graph = new List<int>[n+1];
        for (int i = 1; i <= n; i++)
        {
            graph[i] = new List<int>();
        }
        for (int i = 0; i < lighthouse.GetLength(0); i++)
        {
            int node1 = lighthouse[i, 0];
            int node2 = lighthouse[i, 1];
            graph[node1].Add(node2);
            graph[node2].Add(node1);
        }
        
        DFS(1, 0);
        
        return answer;
    }
    
    public int DFS(int curr, int parent) // 1 : parent가 불 켜야함, 0 : 불 킬 필요 x
    {
        // 리프 노드인 경우
        if (graph[curr].Count == 1 && graph[curr][0] == parent) return 1;
        
        int result = 0;
        for (int i = 0; i < graph[curr].Count; i++)
        {
            // 자식 노드들에 대해 
            int child = graph[curr][i];
            
            if (child == parent) continue; // 인접한 것 중 부모 노드 제외하고 재귀로 불 킬 여부 받기
            result += DFS(child, curr);
        }
        
        // result가 모두 0이면 현재 노드 불 킬 필요 x
        if (result == 0) return 1;
        
        // result가 1 이상이면 현재 노드가 불 켜야 함 
        answer += 1;
        return 0;
    }
}

결과