Lv.3 등대 [JAVA]

문제 링크

성공 여부(걸린 시간): 실패(44분 48초)

아이디어

처음에 다양한 방법에 대해서 생각해봤다. ❌

1. 브루트포스로 등대의 불 켜짐을 전부 탐색 -> X 10만개임 2^100000
2. 리프노드가 있는 경우는 전부 켜주기 ❌

-> 왜냐면 리프노드가 있는 노드라면 무조건 리프노드가 달린 노드에 불이 켜져야함
-> 연결된 간선이 하나인 리프노드를 기억해두고 해당 리프노드가 연결된 노드를 set에 넣고 마지막에 개수를 세어주면 된다.
-> 그러나 0-0-0-0-0-0-0 인 경우엔 3개는 켜져야 하는데 2개 밖에 안켜진다.

3. 리프노드에서 출발해서(0으로) 깊이가 홀수인 노드의 개수를 세어준다. ❌

-> 그렇다면 그래프를 만들어 연결하고 리프노드에서 DFS로 탐색을 진행하며 depth가 홀수일때 hashSet에 add 해주면 된다.
-> add해주는 조건은 이렇다. depth가 홀수이면서 리프노드가 아니여야함

그래서 어떻게 한지 다른 분들의 코드를 참고해봤더니 DFS+DP였다.
내가 제일 자신없는 DFS+DP 이제 극복할때가 온 것 같다.

코드 흐름은 아래와 같다.

1. 그래프 구성
   • graph를 인접 리스트로 초기화하고, lighthouse 간선을 양방향으로 연결.
2. 배열 초기화
   • dp[n+1][2]와 visited[n+1] 준비.
3. DFS 시작
   • 임의 루트(1)에서 DFS(1) 호출.
4. DFS(u) 내부
   • visited[u] = true
   • 기본값 설정: dp[u][0] = 0(u 끔), dp[u][1] = 1(u 켬)
   • 인접 정점 x 순회
     • 이미 방문했으면 건너뜀
     • 미방문이면 DFS(x) 재귀 호출
     • 자식 처리 후 갱신
       • dp[u][0] += dp[x][1]
       • dp[u][1] += Math.min(dp[x][0], dp[x][1])
5. 결과 반환
   • DFS가 끝나면 루트(1)에서 Math.min(dp[1][0], dp[1][1])를 반환.

풀이 코드

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Integer>> graph;
    static boolean [] visited;
    static int [][] dp;

    public int solution(int n, int[][] lighthouse) {
        graph = new ArrayList<>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int [] light: lighthouse){
            graph.get(light[0]).add(light[1]);
            graph.get(light[1]).add(light[0]);
        }
        dp = new int[n+1][2];
        visited = new boolean[n+1];
        DFS(1);
        return Math.min(dp[1][0], dp[1][1]);
    }
    static void DFS(int node){
        visited[node] = true;
        dp[node][0] = 0; // 등대 꺼진 경우
        dp[node][1] = 1; // 등대 켜진 경우
        for(int x: graph.get(node)){
            if(visited[x]){
                continue;
            }
            DFS(x);
            dp[node][0] += dp[x][1];
            dp[node][1] += Math.min(dp[x][0], dp[x][1]);
        }
    }
    //마지막엔 결국 인덱스 1에 전부 저장되게끔 설계
}