[pro] 프로그래머스 level3 133500 등대 (Java) - dp, dfs

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/133500

프로그래머스

 

[풀이]

두 연결된 등대 중 어느 한쪽이 꼭 켜져있어야 할 때, 켜 두어야 하는 등대 개수의 최솟값을 구해야 한다.

 

2가지 경우를 나눠서 생각할 수 있다.

1. 부모 등대가 켜져있다면 자식 등대는 켜둘 수도 있고, 안 켜둘 수도 있다. 켜두는 등대 개수를 줄이기 위해 min 값을 취한다.

2. 부모 등대가 꺼져있다면 자식 등대는 무조건 켜야 한다.

 

비슷한 풀이 방식의 문제: 백준 2522 사회망 서비스

 

[코드]

 

import java.util.*;

class Solution {
    List<List<Integer>> graph = new ArrayList<>();
    boolean[] visited;
    int[][] dp;
    public int solution(int n, int[][] lighthouse) {
        int answer = 0;
        // 윤성이가 켜 두어야 하는 등대 개수의 최솟값을 return 
        
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        
        for(int[] l:lighthouse){
            graph.get(l[0]).add(l[1]);
            graph.get(l[1]).add(l[0]);
        }
        
        visited = new boolean[n+1];
        dp = new int[n+1][2];
        dfs(1);
        
        answer = Math.min(dp[1][0], dp[1][1]);
        
        return answer;
    }
    
    public void dfs(int node){
        visited[node] = true;
        
        dp[node][0] = 0; //부모의 등대가 꺼져있음 -> 자식의 등대는 무조건 켜져야 함
        dp[node][1] = 1; //부모의 등대가 켜져있음 -> 자식의 등대는 켜질수도, 꺼질수도 있음
        
        for(int i=0; i<graph.get(node).size(); i++){
            int child = graph.get(node).get(i);
            
            if(visited[child]) continue;
            
            dfs(child);
            
            dp[node][0] += dp[child][1];
            dp[node][1] += Math.min(dp[child][0], dp[child][1]);
            
        }
    }
    
}