백준 2644 촌수계 파이썬

 

🔗 백준 2644 촌수계 

📌오늘의 학습 키워드

• BFS를 통해 해결하는 문제였으나 자료구조에 따른 메모리 차지에 대해서 알게 되었다.

✨공부한 내용 본인의 언어로 정리하기

• 결론적으로 dictionary가 list보다 메모리를 많이, 통과가 안될 정도로 많이 차지했다.

📚오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지
  • 촌수를 계산하는 문제로 트리를 이용해 BFS로 해결하는 문제였다. 잘 구현했다고 생각했는데 계속 메모리 초과가 났다.
• 어떻게 해결했는지
  • 찾아보니까 나는 dictionary를 사용해 node list를 구현했는데 그게 문제였다. list를 사용하니까 바로 통과했다.
• 무엇을 새롭게 알았는지
  • 메모리 사용량 : dictionary > list

[🤓문제 해결 코드]

import sys
from collections import deque


def find_answer():
    n = int(sys.stdin.readline())
    node_list = []
    visited = []
    for _ in range(n):
        node_list.append([])
        visited.append(False)

    t_1, t_2 = map(int, sys.stdin.readline().split())
    m = int(sys.stdin.readline())

    for _ in range(m):
        parent, child = map(int, sys.stdin.readline().split())
        node_list[parent - 1].append(child)
        node_list[child - 1].append(parent)

    deq = deque()
    deq.append([t_1])
    count = 0
    while deq and count < n:
        nodes = deq.popleft()
        if t_2 in nodes:
            return count
        temp = []
        for node in nodes:
            if not visited[node - 1]:
                temp += node_list[node - 1]
                visited[node - 1] = True

        deq.append(temp)
        count += 1
    return -1


print(find_answer())