인프런 커뮤니티 질문&답변

Ambition님의 프로필 이미지
Ambition

작성한 질문수

코딩테스트 [ ALL IN ONE ]

너비 우선 탐색 (Breadth-first search, BFS)

bfs 코드를 공부하면서 트리에서의 levelorder 구현 방식에 대해 질문이 있습니다.

해결된 질문

작성

·

150

1

from collections import deque

def levelorder(root):
    if root is None:
        return
    visited = []
    q = deque()

    q.append(root)

    while q:
        cur_node = q.popleft()
        visited.append(cur_node.val)

        if cur_node.left:
            q.append(cur_node.left)
        if cur_node.right:
            q.append(cur_node.right)
    return visited

levelorder 코드는 위와 같은데요. 여기서 q.append(root) 를 bfs 코드와 같이 사전에 queue = deque(root)로 미리 넣어줘도 되지 않나요? 이렇게하면 오히려 q.append(root)를 하는데 걸리는 런타임을 더 줄일 수 있을 것 같아서요

답변 1

0

개발남노씨님의 프로필 이미지
개발남노씨
지식공유자

안녕하세요 ambition님

 

미리 넣어줄 수 있으면 넣어주셔도 됩니다. 간혹 deque 생성자의 인자값으로 튜플을 못 넣는다던가 여러가지 예기치 못한 에러가 발생해서 일부로 단계를 나눠서 append를 해줬습니다.

그리고, 런타임을 그렇게 나노단위로 낮출필요는 없습니다 ㅎㅎ

전체적인 시간복잡도를 계산해서 결정하는게 좋습니다.

좋은 의견 감사합니다. :)

Ambition님의 프로필 이미지
Ambition
질문자

아 그렇군요 답변 감사합니다 🙂 어디서 append하는데 연산속도가 느려진다는 글을 보아서요

일단 커리대로 따라간 다음, 문제를 풀면서 시간복잡도를 고려해서 스스로 판단해봐야겠습니다

Ambition님의 프로필 이미지
Ambition

작성한 질문수

질문하기