728x90
https://school.programmers.co.kr/learn/courses/30/lessons/133500
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
- 트리 DP : DFS 풀이
- dp[i][j] : i는 노드번호, j는 등대를 켠 경우와 아닌 경우로 1이면 켠 경우
- 현재 노드가 안켜져 있다면 자식 노드가 켜져있어야 함
- 현재 노드가 켜져 있다면 자식 노드의 값은 상관 없으므로 최솟값을 취함
풀이
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
728x90