[프로그래머스] 등대

https://school.programmers.co.kr/learn/courses/30/lessons/133500?language=java

프로그래머스

• 트리
  • 간선이 n-1개이고, 모든 등대가 서로 다른 등대로 이동 가능하다.
  • 즉, 사이클이 생길 수 없다. 따라서 트리로 바라볼 수 있고 dfs, bfs 같은 트리 순회 방법을 사용할 수 있다.
• 그리디
  • 임의의 한 점을 루트 노드라고 생각하여, dfs를 진행한다고 가정하자. 
  • 가장 아래인 리프 노드는 불이 켜질 필요가 없다. 즉, dfs를 진행하며 가장 아래인 리프 노드까지 내려간 뒤, 리프 노드는 불이 켜질 필요가 없음을 반환한다(1반환).
  • 그리고 특정 한 노드의 여러 자식 노드들 중 하나라도 불이 켜져있지 않으면, 부모 노드인 현재 노드는 불이 켜져야 한다.

import java.util.*;

class Solution {
    
    List<Integer>[] route;
    int answer = 0;
    
    public int solution(int n, int[][] lighthouse) {
        route = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            route[i] = new ArrayList<>();
        }
        
        // route 반영
        for (int[] light : lighthouse) {
            route[light[0]].add(light[1]);
            route[light[1]].add(light[0]);
        }
        
        // dfs(1번 노드를 루트 노드로)
        dfs(1, 0);        
        return answer;
    }
    
    /*
    리프 노드 -> 켜지 X (1 반환)
    
    현재 노드의 자식 노드들의 dfs 합이 0 
        = 자식 노드들이 모두 켠 것 
        -> 현재 노드는 켜지 X (1 반환)
    현재 노드의 자식 노도들의 dfs 합이 0 초과
        = 자식 노드 중 켜지 않은 노드 존재
        -> 현재 노드 켜기 (0 반환)
        
    켤 때마다(0 반환할 때마다) answer++
    */
    private int dfs(int now, int pre) {
        // 리프 노드인 경우 켜지 X (1 반환)
        if (route[now].size() == 1 && route[now].get(0) == pre) {
            return 1; 
        }
        
        // 자식 노드 dfs
        int childSum = 0;
        for (int next : route[now]) {
            if (next == pre) continue;
            childSum += dfs(next, now);
        }
        
        // 자식 노드들의 합이 0 = 모두 켠 것 = 현재 노드 켜지 X
        // 자식 노드들의 합이 1이상 = 하나라도 켜지 않은 것 = 현재 노드 킴 O
        if (childSum == 0) {
            return 1;
        } else {
            answer++;
            return 0;
        }
    }
}