인천 앞바다에는 1부터 n까지 서로 다른 번호가 매겨진 등대 n개가 존재합니다. 등대와 등대 사이를 오가는 뱃길이 n-1개 존재하여, 어느 등대에서 출발해도 다른 모든 등대까지 이동할 수 있습니다. 등대 관리자 윤성이는 전력을 아끼기 위하여, 이 중 몇 개의 등대만 켜 두려고 합니다. 하지만 등대를 아무렇게나 꺼버리면, 뱃길을 오가는 배들이 위험할 수 있습니다. 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.
예를 들어, 아래 그림과 같이 등대 8개와 7개의 뱃길들이 있다고 합시다. 이 경우 1번 등대와 5번 등대 두 개만 켜 두어도 모든 뱃길은 양쪽 끝 등대 중 하나가 켜져 있으므로, 배들은 안전하게 운항할 수 있습니다.
등대의 개수 n과 각 뱃길이 연결된 등대의 번호를 담은 이차원 배열 lighthouse가 매개변수로 주어집니다. 윤성이가 켜 두어야 하는 등대 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
트리 dp 문제의 교과서적인 문제라고 생각한다. n개의 등대, 그리고 등대 사이의 n-1개의 경로 및 등대 간의 통행 보장은 등대가 트리 자료구조를 이루고 있음을 암시한다. 따라서, 트리 탐색을 통해 계층적으로 문제를 풀어나갈 수 있다. 또한 트리의 각 서브트리의 해가 전체 트리의 해를 보장하므로 쪼갤 수 있는 문제애 속한다(각 서브트리의 등대의 불빛 최소값에 따라 전체 등대의 불빛 최솟값이 결정된다). 따라서 dp를 사용할 수 있다.
어떤 서브트리의 루트 노드 등대에 대해 생각해보자. 루트 노드 등대의 경우의 수는 총 두가지이다(켜거나, 끄거나).
첫번째로, 루트 노드 등대를 켜는 경우는 자식 노드가 켜져 있던, 꺼져 있던 제약을 받지 않게 된다. 따라서 (각 자식 노드의 on/off 경우의 수의 최솟값)의 합.+ 1 (루트 노드 등대 역시 켜지므로)로 전체 최솟값이 결정된다.
두 번째로, 루트 노드 등대를 끄는 경우를 생각해보자. 이 경우는 한 뱃길의 양쪽 끝 등대 중 최소 한 등대는 켜져 있어야 한다는 전제조건에 따라, 반대쪽 끝인 자식 노드들은 모두 켜져 있어야 한다. 따라서 (각 자식 노드의 on 경우의 수)의 합이 된다.
이런 식으로 재귀적으로 dp 배열을 채워넣은 뒤, 최종적으로 전체 루트 노드의 dp값의 최솟값을 출력하면 해결된다.
풀이 코드
import sys
sys.setrecursionlimit(100000)
def solution(n, lighthouse):
dp = [[0]*2 for _ in range(n)]
node_dict = { key : [] for key in range(n) }
visited = [False]*n
for a, b in lighthouse :
node_dict[a-1].append(b-1)
node_dict[b-1].append(a-1)
def dfs(node) :
visited[node] = True
leaf_list = list()
for leaf in node_dict[node] :
if visited[leaf] :
continue
leaf_list.append(leaf)
dfs(leaf)
dp[node][0] = 0
dp[node][1] = 1
for leaf in leaf_list :
dp[node][1] += min(dp[leaf])
dp[node][0] += dp[leaf][1]
return
dfs(0)
return min(dp[0])
