[프로그래머스] 등대 (JAVA)

[프로그래머스] 등대

🗒️알고리즘 분류

#valid tree #tree #dfs #트리

📌기억할 만한 포인트

트리(무방향 그래프)에서 각 노드에 대해 “등불을 켜야 하는지” 여부를 판단하여, 최소 개수의 등불(Answer)을 설치하는 문제이다.

dfs 문제이다.

기억할 만한 점은 총 3가지이다.

1. 중간 노드인지 리프 노드인지 확인해야 한다.
   (Graph.get(current).size() == 1 && Graph.get(current).get(0) == previous): 기저 조건: 현재 노드가 리프 노드인 경우. 리프 노드는 부모(previous) 외에 이웃이 없으므로, Graph.get(current).size() == 1이고, 그 유일한 이웃이 previous 이다.
2. DFS는 1 또는 0을 반환한다.
   • 반환값 1: 해당 자식 노드(또는 그 서브트리)가 등불이 켜지지 않아, 부모의 등불이 필요함을 의미한다.
   • 반환값 0: 해당 자식 노드(또는 서브트리)는 이미 등불이 켜져 있어, 부모가 등불을 켤 필요가 없음을 의미한다.
3. shouldLightOn 의 의미 (0 또는 그 이상)
   • shouldLightOn == 0: 모든 자식들이 “부모의 등불 필요 없음” 상태 → 현재 노드는 등불을 켜지 않았으므로 부모가 등불을 켜야 함 (return 1).
   • shouldLightOn > 0: 한 자식 이상에서 “부모의 등불 필요”를 요청 → 현재 노드가 등불을 켜서 자식들을 커버해야 함 (Answer 증가, return 0).

중간 노드인지 리프 노드인지 확인하는 방법을 배운 좋은 문제였다.

📝풀이 코드(JAVA)

import java.util.*;

class Solution {
    ArrayList<ArrayList<Integer>> Graph = new ArrayList<ArrayList<Integer>>();
    private static int Answer = 0;
    
    public int solution(int n, int[][] lighthouse) {
        for (int i = 0; i <= n; ++i) {
            Graph.add(new ArrayList<>());
        }
        
        for (int[] light : lighthouse) {
            int a = light[0];
            int b = light[1];
            Graph.get(a).add(b);
            Graph.get(b).add(a);
        }
        
        dfs(1, 0);
        
        return Answer;
    }
    
    private int dfs(int current, int previous) {
        if (Graph.get(current).size() == 1 && Graph.get(current).get(0) == previous) {
            return 1;
        }
        
        int shouldLightOn = 0;
        
        for (int next : Graph.get(current)) {
            if (next == previous) {
                continue;
            }
            shouldLightOn += dfs(next, current);
        }
        
        if (shouldLightOn == 0) {
            return 1;
        } else {
            ++Answer;
        }
        
        return 0;
    }
}

⏰총 풀이시간

• 120분;;