1068 트리

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

def dfs(trees, remove_list, m):
    # 자식이 없다면 함수를 종료하고 해당 노드의 정보를 추가해서 윗단으로 보내기
    if len(trees[m]) == 0:
        return remove_list + [m]

    # left,right 자식 노드가 있는지 모르니 for문으로 대체하자.
    for child in trees[m]:
        # 자식이 있으니 여기까지 왔고,
        # 그럼 그 자식의 dfs로 들어가야함.
        remove_list = dfs(trees, remove_list, child)

    return remove_list


def solution():
    import sys
    read = sys.stdin.readline

    N = int(read())
    input_list = list(map(int, read().split()))
    M = int(read())

    # tree의 dictionary 초기화
    trees = dict()
    for i in range(N):
        trees[i] = []
        # key의 value들은 key를 부모로 갖는 자식노드들을 뜻한다.

    for child, parent in enumerate(input_list):

        # 동시에 트리에 값을 넣자.
        parent = input_list[child]
        if parent == -1:
            continue
        # 지워질 값은 애초에 넣지 말아볼까
        elif child == M :
            continue
        else:
            trees[parent].append(child)

    # 엥 dict으로 처리하니까 그냥 자식 없는 노드를 세는 방법이 DFS로 탐색하지 않아도 되네?

    # 일단 노드 제거 부분을 구현하자
    # 트리에서 해당 노드(M)으로 child를 뽑아
    # 이 부분을 DFS로 구현해야겠다.
    # DFS로 탐색하다가 자식이 없으면 제거 리스트에 해당 요소를 추가하는 느낌으로?

    remove_list = []
    remove_list = dfs(trees, remove_list, M)
    # 이제 remove_list를 통해 tree dict에서 node제거
    for remove_node in remove_list:
        trees.pop(remove_node)

    # 이제 empty 요소를 측정하자.
    leaf_node_count = list(trees.values()).count([])

    return leaf_node_count


print(solution())

3. 풀이 및 생각

문제 풀이

이 문제는 나는 DFS와 dictionary를 사용해서 풀었다. 원래는 리프 노드가 무엇인지 파악할 때도 DFS를 이용해서 풀어야하나 싶었지만, 노드를 지운다라는 개념을 보았을 때, list를 활용해서 풀게되면, 참 문제가 괴팍해질 것 같았다. 그래서 노드를 지우는 방법을 위해서 list보단 dictionary를 활용하면 좋을 것 같다는 생각이 들었다.

그리고 지울 노드를 선택했을 때, 해당 노드의 하위 노드들을 다 지워야하므로 이때는 DFS를 통해 탐색을 진행했다.

결과적으로 문제를 해결할 수 있었지만, 채점 도중 반례가 존재함을 알게 되었는데, 이것은 트리가 세로 방향으로 한 줄인 경우였다. 이를 해결하기 위해 한가지 트릭을 사용했는데, 그것은 트리를 만들 때, 지울 노드의 부모 노드가 지울 노드를 자식 노드로 갖지 않게 미리 설정하는 것이다. 이렇게 함으로써 모든 반례 또한 해결할 수 있었다.

나의 생각

오 생각보다 점점 트리에 대해 적응해가는 것 같다. 그리고 뭔가 딱 문제를 보면 이렇게 하는게 좋겠다는게 생각나기 시작한거 같다. 조금 뿌듯하다 ㅎㅎ