[프로그래머스] 등대 (트리, DP)

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

프로그래머스

 

분석

• 트리 DP : DFS 풀이
• dp[i][j] : i는 노드번호, j는 등대를 켠 경우와 아닌 경우로 1이면 켠 경우
  • 현재 노드가 안켜져 있다면 자식 노드가 켜져있어야 함
  • 현재 노드가 켜져 있다면 자식 노드의 값은 상관 없으므로 최솟값을 취함

 

유사문제 : https://www.acmicpc.net/problem/2533

2533번: 사회망 서비스(SNS)

 

풀이

import sys
sys.setrecursionlimit(10 ** 9)

def solution(n, lighthouse):
    answer = 0
    
    # 인접리스트
    g=[[] for _ in range(n+1)]
    for s,e in lighthouse:
        g[s].append(e)
        g[e].append(s)
    
    dp=[[0,0] for _ in range(n+1)] # [안켠 경우 최적해, 켠 경우 최적해]
    visited=[False]*(n+1)

    def dfs(x):
        visited[x]=True
        dp[x][1]=1
        
        for i in g[x]:
            if not visited[i]:
                dfs(i) # 자식노드방문
                
                dp[x][0]+=dp[i][1] # 안켠경우 자식노드 켜야함
                dp[x][1]+=min(dp[i][0], dp[i][1]) # 켠경우 최소값
    
    dfs(1)
    answer=min(dp[1][0], dp[1][1])
    
    return answer