[등대/LV3/Python3]

프로그래머스 등대 LV3

 

문제
인천 앞바다에는 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
모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 존재하도록 입력이 주어집니다.

입출력 예

n	lighthouse	result
8	[[1,2], [1,3], [1,4], [1,5], [5,6], [5,7], [5,8]]	2
10	[[4,1], [5,1], [5,6], [7,6], [1,2], [1,3], [6,8], [2,9], [9,10]]	3

 

 

사회망 서비스(SNS)와 동일한 문제이다.

 

 

최대한 등대를 덜 키기 위해, 부모를 켜는 데에 집중하였다.

 

각 등대는 2가지의 행동을 진행하게 된다.

1. 자식이 없거나 자식의 등대가 모두 켜져 있고, 자신의 등대가 꺼져있다면 부모 등대를 킨다.

2. 자식의 여부와 상관없이 자신의 등대가 켜져 있다면, 아무것도 하지 않는다.

 

위 논리를 사용하여 인접한 모든 정점에 불을 킬 수 있도록 구현하였다.

 

import sys
sys.setrecursionlimit(10**6)

def solution(n, lighthouse):
    visit = [0] * (n+1)
    routes = [[] for _ in range(n+1)]
    for u, v in lighthouse:
        routes[u].append(v)
        routes[v].append(u)
    
    def dfs(v):
        visit[v], p = 1, 0
        check = []
        
        for vv in routes[v]:
            if visit[vv] != 0:
                p = vv
                continue
            dfs(vv)
            check.append(vv)
            
        light_cnt = 0
        for vv in check:
            if visit[vv] == 2: light_cnt += 1
        
        if len(check) == light_cnt and visit[v] != 2:
            visit[p] = 2
        
    dfs(1)
    answer = 0
    for i in range(1, n+1):
        if visit[i] == 2: answer += 1
    return answer

 

---

 

최초 아이디어가 항상 최적의 답을 제공하는 것을 직감적으로 알기 어려웠다.