[백준/Python/파이썬] 2533번 사회망 서비스(SNS)

1. 문제

https://www.acmicpc.net/problem/2533

 

2. 배경지식

전형적인 DP 문제이다(진짜 개극혐)

 

Dynamic Programming

• 정의: 큰 문제를 작은 문제로 쪼개어, 큰 문제를 풀 때 활용 → 일명 "기억하며 풀기"
• 조건
  • Overlapping Subproblems(겹치는 부분 문제): 동일한 작은 문제들이 반복하며 나타남(재사용이 가능한 부분이 있어야 함)
  • Optimal Substructure(최적 부분 구조): 부분 문제의 최적 결과값으로 전체 문제의 최적 결과값을 낼 수 있는 경우
• 구현 방식
  1. Bottom-up 방식: 반복문 사용
  2. Top-down 방식: 재귀 사용

 

아래는 실패 코드

class Node:
    def __init__(self, value):
        self.value = value
        self.ea = False
        self.children = []
        self.parent = None


class Tree: 
    def __init__(self, root_node: Node):
        self.root_node = root_node
        self.nodes = {root_node.value: root_node}

    def add(self, parent_val, child_val):
        if parent_val not in self.nodes:
            self.nodes[parent_val] = Node(parent_val)
        parent_node = self.nodes[parent_val]

        if child_val not in self.nodes:
            self.nodes[child_val] = Node(child_val)
        child_node = self.nodes[child_val]

        # 연결
        parent_node.children.append(child_node)
        child_node.parent = parent_node

    def dfs(self, node=None):
        """재귀적 DFS 순회"""
        if node is None:
            node = self.root_node
        print(node.value, end=' ')
        for ch in node.children:
            self.dfs(ch)
    
    def find_leaf_nodes(self, node): # 이건 지피티 도움 받음
        """트리의 모든 리프 노드를 리스트로 반환"""

        if not node.children:
            return [node]

        result = []
        for child in node.children:
            result.extend(self.find_leaf_nodes(child))
        return result
# 이 문제에 한해, 정점 개수가 N개면 간선 개수는 N-1개임
# 즉 u, v 쌍수가 N-1개 주어진다는 것
if __name__ == "__main__":
    N = int(input())
    root_node = Node(1)
    tree = Tree(root_node)

    for _ in range(N-1):
        u, v = map(int, input().split())
        tree.add(u, v)

    # print("DFS:", end=' ')
    # tree.dfs()

    # 바텀업으로 가보자
    leaf_nodes = tree.find_leaf_nodes(tree.root_node)
    # print("리프 노드들:", [node.value for node in leaf_nodes])

    # ea 표시
    total = 0
    for i in range(len(leaf_nodes)):
        leaf = leaf_nodes[i]
        
        if leaf.ea == True:
            if leaf is tree.root_node:
                break
            else:
                continue
        
        else:
            if not leaf.children:
                continue
            else:
                flag = False
                for j in range(leaf.children):
                    if leaf.children[j].ea == True:
                        flag = True
                        break
                
                if not flag:
                    leaf.ea = True
                    total += 1
                else:
                    continue

    print(f"total: {total}")

• total이 자꾸 0으로 출력되는데 이유를 모르겠음
• 바텀업 방식으로 구현하고자 함
• 접근한 중심 논리: 자식 노드 중 하나라도 얼리어답터가 아닌 노드가 있으면 해당 노드는 얼리어답터가 아니고, 자식노드 전부 얼리어답터라면 해당 노드는 얼리어답터가 아님