트리의 부모 찾기 ( 11725번 )

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

 

나의 풀이

from collections import deque
import sys

def _make_tree_list(conn_dict):
    answer = [0] * len(conn_dict)
    answer[0] = 'root'
    queue = deque([1])

    while queue:
        now_n = queue.popleft()
        for i in conn_dict[now_n]:
            if (answer[i - 1] == 0):
                answer[i - 1] = now_n
                queue.append(i)
    return list(map(str,answer))[1:]

def _main(n):
    conn_dict = {}
    for _ in range(n - 1):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        if (a not in conn_dict):
            conn_dict[a] = [b]
        else:
            conn_dict[a].append(b)

        if (b not in conn_dict):
            conn_dict[b] = [a]
        else:
            conn_dict[b].append(a)

    return '\n'.join(_make_tree_list(conn_dict))

n = int(sys.stdin.readline())
print(_main(n))

 

 

시간 복잡도

_make_tree_list(conn_dict) : bfs 함수로 트리를 순회하며 부모노드를 찾음 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n ** 2) )