등대 (Java)

접근 방법

1. (트리) 전체 노드가 N개인데 간선의 숫자는 N-1개만 있기 때문에 사이클이 생길 수 없다. 따라서 등대 간의 연결은 트리로 표현될 수 있고, DFS BFS 등의 트리 순회 방법을 사용할 수 있다.
2. (그리디) 하나의 점을 루트로 삼고, DFS를 실시한다고 가정하자. 리프 노드들을 자식으로 두고 있는 노드가 있다면 해당 노드는 무조건 켜져야 하기 때문에 리프 노드에 도착하면 상위 노드가 무조건 켜져있어야 한다는 시그널을 날려야하기 때문에 1을 반환한다. 리프부터 루트까지 올라가면서 각 노드에서 자식 노드가 하나라도 켜져있지 않다면 무조건 켜줘야하기 때문에 1을 반환한다. 모든 자식 노드가 켜져있다면 효율을 위해서 해당 노드를 꺼야하기 때문에 꺼져있다는 시그널인 0을 반환한다.

코드

import java.util.*;

class Solution {
    private int answer = 0;
    private List<Integer>[] connectedNodes;
    
    private int dfs(int node, int prev) {
        if (connectedNodes[node].size() == 1 && connectedNodes[node].get(0) == prev)
            return 1;
        int net = 0;
        for (int i = 0; i < connectedNodes[node].size(); i++) {
            int next = connectedNodes[node].get(i);
            if (next == prev) continue;
            net += dfs(next, node);
        }
        if (net == 0)
            return 1;
        answer++;
        return 0;
    }
    
    public int solution(int n, int[][] lighthouse) {
        connectedNodes = new ArrayList[n + 1];
        for (int i = 1; i < n + 1; i++) connectedNodes[i] = new ArrayList<>();
        for (int[] edge : lighthouse) {
            int a = edge[0]; int b = edge[1];
            connectedNodes[a].add(b);
            connectedNodes[b].add(a);
        }
        dfs(1, 0);
        return answer;
    }
}

참고

https://velog.io/@ddongh1122/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%93%B1%EB%8C%80

[프로그래머스] 등대