[프로그래머스] 등대 : unsolved

       문제 요약        

- 문제

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

         아이디어        

한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.

??? 이 문장을 보고 무슨 소리인가 했다 

결국 간선을 잇는 노드 중 하나는 반드시 불이 켜져야 하는 의미

다른 사람)

전체 노드가 N개인데 간선의 숫자는 N-1개만 있기 때문에 사이클이 생길 수 없다.

따라서, 등대 간의 연결은 트리로 표현될 수 있다

 

+ 리프 노드일 경우

결과 1 리턴 (불을 켜지 않음)

 

+ 리프 노드가 아닐 경우 

자식 노드를 대상으로 DFS 진행

자식 노드가 모두 불을 켠다면 해당 노드가 불을 킬 필요가 없으므로 1리턴

자식 노드 중 불을 켜지 않은 노드가 1개 이상이라면 (= 리턴 합이 0이 아님) 해당 노드가 불을 켜야 하므로 0리턴 

 

         소스코드        

 

 

import java.util.*;
class Solution {
    static int answer = 0;
    static List<Integer>[] adj;
    public int solution(int n, int[][] lighthouse) throws Exception{
        
        adj = new ArrayList[n+1];
        for(int i = 0; i < n+1; i++) {
            adj[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < n-1; i++) {
            adj[lighthouse[i][0]].add(lighthouse[i][1]);
            adj[lighthouse[i][1]].add(lighthouse[i][0]);
        }
        
        dfs(1, 0);
        return answer;
    }
    private int dfs(int node, int prev) {
        if(adj[node].size() == 1 && adj[node].get(0) == prev) {  // 리프노드인 경우, 불을 켜지 않는다
            return 1;
        }
        int net = 0;
        for(int i = 0; i < adj[node].size(); i++) {
            int next = adj[node].get(i);
            if(next == prev)continue;
            net += dfs(next, node);
        }
        if(net == 0)return 1; // 자식노드가 모두 불을 켠 경우, 현재 노드는 불을 킬 필요가 없다 
        answer += 1;
        return 0; // 그 외의 경우 현재 노드는 반드시 불을 켜야 한다
    }
}