백준 1967: 트리의 지름 ( BFS / with Python)
문제를 읽고나면, 모든 노드 간 거리를 구해, 그 중 가장 긴 거리를 답으로 내면 될 것이라 생각하여 "Floyd-Warshall"알고리즘을 사용해야하는 문제로 생각할 수 있다. 가능하겠지만, 메모리 제한에 무조건 걸리게 된다. (4Byte * 10000 * 10000)하면 이미 400MB를 넘어가기 때문.. ) 가장 중요한 포인트는 "BFS로 진행을 하되, BFS의 input으로 leaf노드들만 넣어주면 된다는 것"이다. 그마저도 python3로는 시간초과 판정이 나오니, pypy3으로 제출하였다.
Python알고리즘
2023. 10. 14. 16:20
