[Python] Baekjoon - 11725. 트리의 부모 찾기

백준 11725번 트리의 부모 찾기 문제는 노드가 N개인 트리의 간선이 주어질 때 모든 노드의 부모를 구하는 문제다. 그래프 탐색을 통해 해결할 수 있는 문제인데 시간 초과 또는 메모리 초과가 되지 않도록 주의하며 풀어야 한다. 난이도는 실버 2이다.

 

백준 11725번 트리의 부모 찾기 문제 정보

알고리즘 분류

- 트리 및 그래프 탐색

난이도

- 실버 2

 

트리의 부모 찾기 문제 요약

노드가 N개이고 1이 루트인 트리의 간선 N-1개가 입력될 때, 2~N번 노드의 부모를 각각 출력하는 문제다.

 

문제 풀이 과정

방식 1 (시간 초과)

• 처음에는 edge를 따로 저장하지 않고 입력받을 때마다 이전까지 연결된 트리에 연결하는 방식을 사용했다. 부모가 정해진 노드들의 부모 정보를 저장하는 딕셔너리와, 부모를 아직 정할 수 없는 노드 쌍을 저장하는 레디큐를 사용했다.
• 레디큐를 순환적으로 돌면서 트리를 채워가는 과정이 너무 오래 걸려서 시간 초과가 발생했다.

 

방식 2 (메모리 많이 차지)

두 번째도 edge를 저장하지 않는 방식이었다. 앞서 사용한 레디큐 대신 아직 트리에 연결되지 못한 edge를 저장하는 리스트를 만들고, 부모를 찾은 노드에 대해 아직 연결 안 된 edge를 트리에도 재귀적으로 붙여주는 방식으로 작성했다. 답은 맞았지만 메모리가 많이 들고 시간이 오래 걸렸다.

 

방식 3 (모범 답안)

앞선 방식으로 답을 맞히고, 효율적인 코드를 위해 모범 답안 코드를 참고하여 방식을 수정하였다. 입력받은 edge들을 전부 리스트로 저장. 루트인 1번 노드부터 dfs 방식으로 자식들을 찾아서 등록하는 과정을 반복했다.

 

코드

코드 설명

• parent_of_node[i]: i번 노드의 부모를 저장한다. 아직 발견하지 못한 경우 0으로 초기화되어있다.
• link_of_node[i]: i번 노드와 연결된 노드들의 리스트를 저장한다(부모, 자식 전부 포함).

import sys


def get_parents():
    global parent_of_node, link_of_node

    stack = [1]
    parent_of_node[1] = 1

    # node 1부터 자식들을 찾아서 parent_of_node에 등록하고 stack에 추가
    while stack:
        parent = stack.pop()

        for child in link_of_node[parent]:
            if parent_of_node[child]:
                continue
            parent_of_node[child] = parent
            stack.append(child)


if __name__ == '__main__':
    N = int(input())
    parent_of_node = [0 for _ in range(N+1)]
    link_of_node = [[] for _ in range(N+1)]

    for _ in range(N-1):
        node1, node2 = map(int, sys.stdin.readline().split())
        link_of_node[node1].append(node2)
        link_of_node[node2].append(node1)

    get_parents()

    for parent in parent_of_node[2:]:
        print(parent)