[프로그래머스] 등대

문제 이해하기

인천 앞바다에는 등대와 등대 사이를 오가는 뱃길이 총 n-1개 있는 등대가 n개 있습니다. 윤성이는 전력을 아끼기 위해 일부 등대만 켜둘 계획입니다. 그러나 모든 뱃길이 안전하게 운항하기 위해서는 각 뱃길의 양쪽 끝에 적어도 하나의 등대가 켜져 있어야 합니다.

 

문제 해결 아디어

1. leaf 노드를 불을 꺼야 함으로 먼저 leaf노드를 찾습니다.  다음과 같이 더이상 dfs로 진입할 곳이 없다면 해당 노드는 leaf노드가 됩니다.

def dfs(graph, node, visited, lighthouses):
    for next_node in graph[node]:
        if not visited[next_node]:
            dfs(graph, next_node, visited, lighthouses)

 

2. 그 후 현재 노드를 기준으로 자식 노드들 중 하나라도 꺼져있으면 해당 노드의 등대를 켜야합니다.

    for next_node in graph[node]:
        if not visited[next_node]:
            lighthouse_status.append(dfs(graph, next_node, visited, lighthouses))

    if 1 <= lighthouse_status.count(False):
        lighthouses[node] = True
        return True

 

 

코드

import sys
sys.setrecursionlimit(100001)
from collections import deque


def dfs(graph, node, visited, lighthouses):
    lighthouse_status = []
    visited[node] = True
    need_turn_on = False
    
    for next_node in graph[node]:
        if not visited[next_node]:
            lighthouse_status.append(dfs(graph, next_node, visited, lighthouses))

    if 1 <= lighthouse_status.count(False):
        lighthouses[node] = True
        return True
        
    return need_turn_on

def solution(n, lighthouse):
    answer = 0
    
    graph = [[] * n for _ in range(n + 1)]
    lighthouses = [False] * (n + 1) 
    visited = [False] * (n + 1)
    
    for start, end in lighthouse:
        graph[start].append(end)
        graph[end].append(start)
        
    dfs(graph, lighthouse[0][0],visited, lighthouses)

    count_true = lighthouses.count(True)
    return count_true


if __name__ == "__main__":
    n = 8
    lighthouse = [[1, 2], [1, 3], [1, 4], [1, 5], [5, 6], [5, 7], [5, 8]]
    print(solution(n, lighthouse))

 

배운점 정리하기

그래프가 결국 트리로 변환할 수 있고, 트리에서는 하위 집합의 정보를 탐색하기 편해진다