[프로그래머스] 등대

해설

• 노드가 N개인데 N-1개로 모두 연결되어있다 => 트리구조
• 트리를 만든다.
• 트리에서 가장 끝의 리프는 불을 키지 않는다.
• 자식노드가 모두 불이 꺼져있으면 불을킨다
• 자식노드가 하나라도 불이꺼져있으면 불을 킨다

 

 

처음에 루트노드를 무조건 자식이 2개 이상인걸로 잡았다.

그런데 다시 문제를 풀어보니 루트노드는 아무거나 잡아도 상관없어서 1로 맘편하게 했다

from collections import deque
import sys
sys.setrecursionlimit(10**9)
class Tree:
    def __init__(self,num):
        self.num = num
        self.childs = []
        self.parentNode = None       
    def printChilds(self):
        result = ""
        for i in self.childs:
            result += str(i.num)+" "
        print(self.num)
        print(result if result != "" else "none")

def getRootNode(n, adj):
    rootNode = None
    for i in range(1, n+1):
        if len(adj[i]) > 1:
            return Tree(i)
    if rootNode is None:
        return Tree(1)

def makeTree(n, adj, rootNode):
    q = deque()
    q.append(rootNode)
    visit = [False] *(n+1)
    while q:
        node = q.popleft()
        now = node.num
        if visit[now]:
            continue
        visit[now] = True
        for near in adj[now]:
            if not visit[near]:
                childNode = Tree(near)
                node.childs.append(childNode)
                q.append(childNode)
        #node.printChilds()

class answerObserver:
    def __init__(self):
        self.answer = 0

def dfs(node, observer):
    if len(node.childs) == 0:
        return False
    isTurnOn = True
    
    for child in node.childs:
        isTurnOn &= dfs(child,observer)
        
    isTurnOn = not isTurnOn
    if isTurnOn:
        observer.answer+=1
        #print(node.num,"은 켜야됨")
    return isTurnOn
    
    
def solution(n, lighthouse):
    adj = [[] for _ in range(n+1)]
    for A,B in lighthouse:
        adj[A].append(B)
        adj[B].append(A)
    #rootNode = getRootNode(n, adj)
    rootNode=Tree(1)
    makeTree(n, adj, rootNode)
    observer = answerObserver()
    dfs(rootNode,observer)
    return observer.answer