등대 !

 

사용 알고리즘: dfs

사용 언어: java

 

우왕... 이걸 이제 풀었따

import java.util.*;
class Solution {
    boolean[] lit;
    List<Integer>[] list;
    
    public int solution(int n, int[][] lighthouse) {
        init(n, lighthouse);
        
        dfs(1, 1);
        
        int answer = 0;
        for(int i=1; i<n+1; i++) {
            if(lit[i])
                answer++;
        }
        return answer;
    }
    
    public int dfs(int node, int prev) {
        if(list[node].size()==1 && prev == list[node].get(0)) {
            return 1;
        }
        
        int sum = 0;
        for(int nxt: list[node]) {
            if(prev == nxt) continue;
            sum += dfs(nxt, node);
        }
        
        if(sum > 0) {
            lit[node] = true;
            return 0;
        }
        return 1;
    }
    
    public void init(int n, int[][] lighthouse) {
        lit = new boolean[n+1];
        list = new ArrayList[n+1];
        for(int i=0; i<n+1; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i=0; i<n-1; i++) {
            list[lighthouse[i][0]].add(lighthouse[i][1]);
            list[lighthouse[i][1]].add(lighthouse[i][0]);
        }
    }
}

 

여기서 변형이 좀만 되도 풀 수 있을지 의문이긴 한데...

일단 등대는 풀 수 있게 되었따..

몇 트 만이지