[프로그래머스] - 등대 [파이썬]

그냥 감도 못 잡았던 문제.. 모든 경우의 수를 다 탐색해야 해서 DFS나 BFS나 아무튼 완전탐색을 돌려야겠다고 생각했는데

노드와 간선이 최대 10만개까지 되니까 이게 맞나?라고 생각되기도 했었음

https://school.programmers.co.kr/learn/courses/30/lessons/133500

프로그래머스

문제 설명

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

---

해설

일단 직관적으로 모든 노드에 대하여 해당 노드가 켜졌냐?, 꺼졌냐?를 생각하여 답을 도출하면 된다.
따라서 각 단계별로 꺼졌을때 결과와 켜졌을때 결과 2가지 값을 넘겨주거나 반환받아야 한다.

def solution(n, lighthouse):
    graph = [[] for _ in range(n)]
    visited = [False] * n
    for a, b in lighthouse:
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    answer = min(dfs(0, graph, [False for _ in range(n)]))


    return answer



def dfs(node, graph, visited):
    visited[node] = True
    children = []
    for nextNode in graph[node]:
        if not visited[nextNode]:
            children.append(nextNode)

    # 켯을때, 안켯을때 경우를 밑에서부터 계속 합산해 가야됨
    on, off = 1, 0

    # 제일 변두리에 있는 애들
    if len(children) == 0:
        return on, off
    else:
        for child in children:
            child_on, child_off = dfs(child, graph, visited)
            # 만약 현재 노드가 켜져 있다? 내 아래에서 발생한 가장 작은 결과를 합산하면 됨
            on += min(child_on, child_off)  
            # 만약 현재 노드가 꺼져 있다? 그러면 자식 노드중에서 켜져 있는 결과를 합산하면 됨
            off += child_on
        return on, off

 

BFS로도 풀어볼까 했는데 잘 안풀린다.
가지 하나 하나씩 경우의 수를 완결?완성? 시켜야지 다음 가지의 경우의 수를 파악 가능한데, BFS는 아무래도 가지를 먼저 훑다 보니 중복되는 경우가 생기며 최적의 답을 구하지 못하는 것 같다.