p_홀짝트리_388354

문제

https://school.programmers.co.kr/learn/courses/30/lessons/388354?language=python3

답

1차답

"""
홀짝 트리 : 노드번호의 홀짝여부와 자식노드의 개수의 홀짝여부가 일치
역 ~ : ~가 반대
모두다 트리긴함<< 사이클이ㅣ없음
하나씩 루트노드로지정해서
"""
import copy

def solution(nodes, edges):
    dic = {}
    answer = [0,0]
    for n in nodes:
        dic[n]=[]
    for e in edges:
        dic[e[0]].append(e[1])
        dic[e[1]].append(e[0])
    for n in nodes:
        data=checkTree(n,copy.deepcopy(dic),None)
        if data != 0:
            answer[data-1] +=1
        # print("결과",n,data,answer)
    
    return answer

def checkTree(root,dic,isHoljjak):
    # print(id(dic))
    # isHoljjak : 1- 홀짝, 2-역홀짝
    if isHoljjak is None:
        # 루트노드
        childLen = len(dic[root])
        if root%2 == childLen%2:
            isHoljjak = 1
        else:
            isHoljjak = 2
    else:
        # 자식노드
        childLen = len(dic[root]) - 1  # 부모 제외
        if root%2 == childLen%2:
            if isHoljjak != 1:
                return 0
        else:
            if isHoljjak != 2:
                return 0
    
    # 자식들 확인
    for child in dic[root]:
        dic[child].remove(root)
        result = checkTree(child, dic, isHoljjak)
        if result == 0:
            return 0
    
    return isHoljjak

2차답

def solution(nodes, edges):
    dic = {}
    answer = [0,0]
    for n in nodes:
        dic[n]=[]
    for e in edges:
        dic[e[0]].append(e[1])
        dic[e[1]].append(e[0])
    
    holjjak = [0, 0]  # [홀짝 트리 수, 역홀짝 트리 수]
    
    for node in nodes:
        try:
            result = checkTree(node, dic.copy(), None)
            if result != 0:
                holjjak[result-1] += 1  
        except:
            pass

    return holjjak

3차답
아마 각노드마다 2가지경우가 있을 것같다

1. 루트노드인경우
2. 루트노드가아닌경우
   이렇게해서 저장을하고돌려야할것같다
   아님아님

4차답
레전드 한트리에 하나의 루트노드면 특정트리임
그래서 루트일때자식일때 어떤노드인지 받아놓고
한트리내에서 루트일때 A 자식일때 다 B면
또 뻐킹 런타임에러가난다.
근데 조금 개선되엇다.
그냥queue를이용하는측면이ㅓㅇ떤가싶다.

def solution(nodes, edges):
    graph = {n: [] for n in nodes}
    visited = set()
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    holjjakDic = {}
    # 보닌이 홀찍인지 역홀짝인지
    for n in nodes:
        childLen = len(graph[n])
        a = n%2
        b = childLen%2
        c = (childLen-1)%2
        # 루트일때 자식일때
        holjjakDic[n] = [1 if a==b else 2,1 if a==c else 2]
    
    # print(holjjakDic)
    
    holjjak = [0, 0]  # [홀짝 트리 수, 역홀짝 트리 수]

    def dfs(node,dic):
        if node in visited:
            return False
        visited.add(node)
        r,c=holjjakDic[node]
        Rkey = f'R{r}'
        Ckey = f'C{c}'
        dic[Rkey].append(node)
        dic[Ckey].append(node)
        for child in graph[node]:
            dfs(child,dic)

    for node in nodes:
        if node in visited:
            continue
        dic = {
            "R1":[],
            "R2":[],
            "C1":[],
            "C2":[],
        }
        dfs(node, dic)
        if len(dic["R1"]) == 1:
            holjjak[0] +=1
        if len(dic["R2"]) == 1:
            holjjak[1] +=1
        # print(node,dic)
    return holjjak

5차답안 (성공!)
역시 재귀는 쓰래기다
라고하면안되겟죠?
depth가 커져서 메모리를 많이잡아 먹어 에러가 나는거 같다.
따라서 dfs에서 bfs
즉 queue와 while문을 이용하엿더니 통과하였다.

from collections import deque

def solution(nodes, edges):
    graph = {n: [] for n in nodes}
    visited = set()
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    holjjakDic = {}
    # 보닌이 홀찍인지 역홀짝인지
    for n in nodes:
        childLen = len(graph[n])
        a = n%2
        b = childLen%2
        c = (childLen-1)%2
        # 루트일때 자식일때
        holjjakDic[n] = [1 if a==b else 2,1 if a==c else 2]
    
    # print(holjjakDic)
    
    holjjak = [0, 0]  # [홀짝 트리 수, 역홀짝 트리 수]
    dic = {}
    for node in nodes:
        if node in visited:
            continue
        dic = {
            "R1":[],
            "R2":[],
            "C1":[],
            "C2":[],
        }
        queue = deque([node])
        while len(queue)>0:
            # print(queue)
            k = queue.popleft()
            if k in visited:
                continue
            visited.add(k)
            r,c=holjjakDic[k]
            Rkey = f'R{r}'
            Ckey = f'C{c}'
            dic[Rkey].append(k)
            dic[Ckey].append(k)
            for child in graph[k]:
                if child not in visited:
                    queue.append(child)
        if len(dic["R1"]) == 1:
            holjjak[0] +=1
        if len(dic["R2"]) == 1:
            holjjak[1] +=1
        # print(node,dic)
    return holjjak