[SWEA] 1855. 영준이의 진짜 BFS - 파이썬 풀이

부모 자식을 defaultdict로 저장해서 수행했을 때는 시간초과가 났다.

그런데 그냥 단순히 리스트로 하니까 해결되었다.

 

풀이1: defaultdict로 했을 경우 시간 초과

BFS는 큐에 서치할 노드를 담아서 진행됨

부모 노드를 key로, 자식을 value로 갖는 dict인 parent_child와

자식을 key로, 부모노드를 value로 갖는 dict인 child_parent를 저장.

그리고 각 노드의 depth (LCA (Least Common Ancestor)를 수행하기 위함)을 저장함.

 

아래는 시간초과 코드

from collections import defaultdict, deque
# import sys
# sys.stdin = open("sample_input.txt", "r")

T = int(input())

def lca(node1, node2):
    global answer
    while depth[node1] > depth[node2]:
        answer += 1
        node1 = child_parent[node1]
    while depth[node1] < depth[node2]:
        answer += 1
        node2 = child_parent[node2]
    while node1 != node2:
        answer += 2
        node1 = child_parent[node1]
        node2 = child_parent[node2]
    return

for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////

    answer = 0
    N = input()
    input_list = list(map(int, input().split()))

    i = 2
    parent_child = defaultdict(list)
    child_parent = defaultdict(int)
    depth = defaultdict(int)
    depth[1] = 1
    for parent in input_list:
        parent_child[parent].append(i)
        child_parent[i] = parent
        depth[i] = depth[parent] + 1
        i += 1

    queue = deque([1])
    # queue.extend(parent_child[1]) # 일단 루트 노드의 자식 노드들부터 큐에 넣어준다
 
    cur_node = 1
    while queue:
        search_node = queue.popleft()
 
        # if len(parent_child[search_node]) != 0: # 탐색 노드의 자식을 큐의 끝에 넣어준다
        #     queue.extend(parent_child[search_node])
 
        for child in parent_child[search_node]:
            queue.append(child)
            lca(cur_node, child)
            cur_node = child

    print(f"#{test_case} {answer}")
    # ///////////////////////////////////////////////////////////////////////////////////

 

---

 

아래는 pass 코드

 

풀이2: list로 initialize 할 경우 통과

from collections import deque
 
T = int(input())
 
def lca(node1, node2):
    global answer
    while depth[node1] > depth[node2]:
        answer += 1
        node1 = child_parent[node1]
    while depth[node1] < depth[node2]:
        answer += 1
        node2 = child_parent[node2]
    while node1 != node2:
        answer += 2
        node1 = child_parent[node1]
        node2 = child_parent[node2]
    return
 
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
 
    answer = 0
    N = int(input())
    input_list = list(map(int, input().split()))
 
    i = 2

    parent_child = [[] for _ in range(N+1)]
    child_parent = [0] * (N+1)
    depth = [0] * (N+1)
 
    depth[1] = 1
    for parent in input_list:
        parent_child[parent].append(i)
        child_parent[i] = parent
        depth[i] = depth[parent] + 1
        i += 1
 
    queue = deque([1])
    # queue.extend(parent_child[1]) # 일단 루트 노드의 자식 노드들부터 큐에 넣어준다
 
    cur_node = 1
    while queue:
        search_node = queue.popleft()
 
        for child in parent_child[search_node]:
            queue.append(child)
            lca(cur_node, child)
            cur_node = child
 
    print(f"#{test_case} {answer}")