[Level 3] 등대(Python)

 

프로그래머스

문제

1~n까지 서로 다른 번호가 매겨진 등대 n개가 존재한다.
뱃길은 n-1개 존재하며, 어느 등대에서 출발해도 다른 모든 등대까지 이동할 수 있다.
한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져있도록 등대를 켜두어야 한다.

 

<제한 사항>

- 2 ≤ n ≤ 100,000
- lighthouse의 길이 = n – 1
- lighthouse 배열의 각 행 [a, b]는 a번 등대와 b번 등대가 뱃길로 연결되어 있다는 의미
- 1 ≤ a ≠ b ≤ n
- 모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 존재하도록 입력이 주어진다.

 

풀이 과정

풀이 시간: 2시간 이상 접근하다 포기하고 접근방법 참고

알고리즘: DP + BFS

1. DP 테이블 정의

- dp[node][0]: node가 꺼져있을 때, node를 루트로 하는 서브트리에서 최소로 불이 켜진 개수

- dp[node][1]: node가 켜져있을 때, node를 루트로 하는 서브트리에서 최소로 불이 켜진 개수

 

2. 초기값 정의

dp[node][0] = 0

dp[node][1] = 1

 

3. 점화식

dp[node][0] += dp[child][1]

- node가 꺼져있기 때문에 child가 켜져있어야 함

dp[node][1] += min(dp[child][0], dp[child][1])

- node가 켜져있을 때, child가 켜지거나 꺼지거나 더 작은 걸 선택

 

<시간 복잡도>

1. 그래프 정의: O(n)

2. DFS 순회: O(n)

3. DP 테이블 업데이트: O(n)

-> O(n) + O(n) + O(n) = O(n)

 

코드

DFS(재귀방식 구현) 

재귀로 구현할 경우, 재귀 깊이를 변경해줘야 시간초과가 나지 않는다.

import sys
sys.setrecursionlimit(100000)


def dfs(node, parent, graph, dp):
    dp[node][0] = 0 # 해당 노드에 불이 꺼져있을 때, node를 루트로 하는 서브트리에서 최소로 불이 켜진 개수
    dp[node][1] = 1 # 해당 노드에 불이 켜져있을 때, node를 루트로 하는 서브트리에서 최소로 불이 켜진 개수

    for child in graph[node]:
        if child == parent:
            continue
        dfs(child, node, graph, dp)

        dp[node][0] += dp[child][1] # 자식 노드들이 켜져있어야 하므로
        dp[node][1] += min(dp[child][0], dp[child][1]) # 자식 노드들이 꺼져있거나 켜져있을 수 있으므로
        
        
def solution(n: int, lighthouse: list) -> int:
    tree = [[] for _ in range(n+1)]

    for a, b in lighthouse:
        tree[a].append(b)
        tree[b].append(a)

    # DP 테이블 정의
    dp = [[0, 0] for _ in range(n+1)]

    dfs(1, -1, tree, dp)

    return min(dp[1])

 

DFS(스택 방식 구현)

def dfs_stack(start_node, graph, dp):
    stack = [(start_node, -1)]
    order = []

    while stack:
        node, parent = stack.pop()
        order.append((node, parent))
        for child in graph[node]:
            if child != parent:
                stack.append((child, node))

    # 역순으로 순회하며 DP 업데이트
    while order:
        node, parent = order.pop()
        dp[node][0], dp[node][1] = 0, 1
        for child in graph[node]:
            if child != parent:
                dp[node][0] += dp[child][1]
                dp[node][1] += min(dp[child][0], dp[child][1])


def solution(n: int, lighthouse: list) -> int:
    tree = [[] for _ in range(n+1)]

    for a, b in lighthouse:
        tree[a].append(b)
        tree[b].append(a)

    # DP 테이블 정의
    dp = [[0, 0] for _ in range(n+1)]

    dfs_stack(1, tree, dp)

    return min(dp[1])

 

처음에 그리디로 접근해서 풀이했다.
각 리프노드의 부모 노드를 모두 켜주는 식으로 진행하면 된다고 생각했고, 반례를 찾지 못했다.
결국에 아이디어를 참고해서 DP로 접근해야 한다는 것을 확인했다.

동적 프로그래밍(DP) 접근법은 각 노드의 상태를 정의하고, 모든 가능한 선택을 고려하여 최적의 해를 계산할 수 있다.

특히, DFS + DP를 사용하면 각 노드가 켜져 있는 경우와 꺼져 있는 경우를 모두 고려할 수 있기 때문에, 단순히 현재 단계에서 최적의 선택을 하는 그리디와 달리, 전체 트리 구조를 고려해 최적의 해를 보장할 수 있다.

 

반례 계속 못찾다가, n=8, lighthouse=[[1, 2], [2, 5], [1, 4], [4, 6], [1, 3], [3, 7], [7, 8]]

이 반례를 찾을 수 있었다. 여기에 누군가 아주 친절하게 그림까지 그려주셨는데, 내가 처음에 짠 그리디로 풀이하면 해당 결과를 3으로 반환하기 때문에 틀린 코드가 된다는 것을 확인할 수 있다.

트리 순회의 경우 DFS를 재귀 방식과 스택 방식 모두 구현해서 제출해봤는데 재귀 방식이 약간 더 빠른 걸 확인할 수 있었다. (하지만, 여전히 재귀 깊이를 늘려주지 않으면 시간초과 난다.)