고정 헤더 영역
상세 컨텐츠
본문
문제를 읽고나면, 모든 노드 간 거리를 구해, 그 중 가장 긴 거리를 답으로 내면 될 것이라 생각하여
"Floyd-Warshall"알고리즘을 사용해야하는 문제로 생각할 수 있다.
가능하겠지만, 메모리 제한에 무조건 걸리게 된다.
(4Byte * 10000 * 10000)하면 이미 400MB를 넘어가기 때문.. )
가장 중요한 포인트는
"BFS로 진행을 하되, BFS의 input으로 leaf노드들만 넣어주면 된다는 것"이다.
그마저도 python3로는 시간초과 판정이 나오니, pypy3으로 제출하였다.
'Python알고리즘' 카테고리의 다른 글
| 백준 2211: 네트워크 복구 (Dijkstra / with Python) (0) | 2023.10.14 |
|---|---|
| 백준 1719: 택배 (Floyd-Warshall / with Python) (0) | 2023.10.14 |
| 백준 15686: 치킨 배달 (BackTracking / with Python) (0) | 2023.10.14 |
| 백준 2473: 세 용액 ( 투포인터 / with Python ) (0) | 2023.10.14 |
| 백준 12865: 평범한 배낭 (DP / with Python) (0) | 2023.10.14 |
