문제 설명 및 제한사항
문제 설명
인천 앞바다에는 1부터 n까지 서로 다른 번호가 매겨진 등대 n개가 존재합니다. 등대와 등대 사이를 오가는 뱃길이 n-1개 존재하여, 어느 등대에서 출발해도 다른 모든 등대까지 이동할 수 있습니다. 등대 관리자 윤성이는 전력을 아끼기 위하여, 이 중 몇 개의 등대만 켜 두려고 합니다. 하지만 등대를 아무렇게나 꺼버리면, 뱃길을 오가는 배들이 위험할 수 있습니다. 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.
예를 들어, 아래 그림과 같이 등대 8개와 7개의 뱃길들이 있다고 합시다. 이 경우 1번 등대와 5번 등대 두 개만 켜 두어도 모든 뱃길은 양쪽 끝 등대 중 하나가 켜져 있으므로, 배들은 안전하게 운항할 수 있습니다.
등대의 개수 n과 각 뱃길이 연결된 등대의 번호를 담은 이차원 배열 lighthouse가 매개변수로 주어집니다. 윤성이가 켜 두어야 하는 등대 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
•
2 ≤ n ≤ 100,000
•
lighthouse의 길이 = n – 1
◦
lighthouse 배열의 각 행 [a, b]는 a번 등대와 b번 등대가 뱃길로 연결되어 있다는 의미입니다.
▪
1 ≤ a ≠ b ≤ n
▪
모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 존재하도록 입력이 주어집니다.
아이디어 및 해결 방법
정답 상황에서, 어떤 노드 하나는 꺼지거나 켜지거나 둘 중 하나일 겁니다. 그러면 문제를 분할해서, 자신을 포함한 서브트리에서 그 노드가 켜졌을 때의 최소 점등 등대 개수(on)와, 그 노드가 꺼졌을 때의 최소 점등 등대 개수(off)를 구해서 둘 중 작은 것을 답으로 내놓는다고 생각해 봅시다. 이걸 루트 노드에 대해서 구하면 정답이 될 겁니다.
on, off 값을 구하기 위해서, 어떤 노드와 그 자식 노드와의 관계성을 생각해볼 수 있습니다.
해당 노드가 켜졌을 때, 그 노드를 포함한 서브트리의 최소 점등 등대 개수(on)
어떤 노드가 켜져있다면, 자식 노드는 켜져 있든말든 상관 없습니다. 따라서 자식노드를 루트 노드로 하는 DFS로 얻은 child_on, child_off 값중 작은 값을 골라서 합쳐 줍니다.
해당 노드가 꺼졌을 때, 그 노드를 포함한 서브트리의 최소 점등 등대 개수(off)
어떤 노드가 꺼져 있다면, 자식 노드는 무조건 켜져있어야 합니다. 따라서 자식 노드의 child_on 값만 취하여 합쳐 줍니다.
루트 노드 (루트 노드로 아무 노드나 잡아도 됩니다) DFS로 트리를 순회하면서 위 관계를 생각하면서 on, off 값을 구하는 것을 재귀적으로 수행하면 min(on, off) 로 답을 얻을 수 있습니다.
코드
import sys
from collections import defaultdict
sys.setrecursionlimit(1000001)
A = defaultdict(list)
vis = [False] * 1000001
# 자신을 포함한 subtree에서, 내가 켜졌을 때의 최소 점등 등대 개수와
# 내가 꺼졌을 때의 최소 점등 등대 개수를 반환합니다.
def dfs(u):
vis[u] = True
if not A[u]:
# u가 leaf라면 내가 켜졌을 떄의 최소 점등 등대 개수는 1
# 내가 꺼졌을 때의 최소 점등 등대 개수는 0
return 1, 0
# u가 leaf가 아니라면
on, off = 1, 0
for v in [v for v in A[u] if not vis[v]]:
# 내가 켜졌다면 child들은 켜지든 꺼지든 상관 없습니다. -> 킨 것과 끈 것중 최소값을 취함
# 내가 꺼졌다면 child들은 무조건 켜져야 합니다.
# 이 점을 생각해서 leaf들의 정보를 취합, 정리합니다.
child_on, child_off = dfs(v)
on += min(child_on, child_off)
off += child_on
return on, off
def solution(n, lighthouse):
for u, v in lighthouse:
A[u].append(v)
A[v].append(u)
on, off = dfs(1)
return min(on, off)
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges