[질문] 어디서 시간 더 줄일 수 있는지 힌트좀

익명(210.91) 2021-09-15 19:53 추천 1

힌트점

adj 배열이 O(n^2)을 차지하고 있는 거 같은데 adj를 안쓰고 할 수 있지 않을까?

익명(27.35) 2021-09-15 23:51
답글
가령 인접 리스트라던가 인접 리스트라던가..

익명(27.35) 2021-09-15 23:57
답글
순간이동하는 경우가 있는데 어떻게 처리해야 될까

익명(210.91) 2021-09-16 08:16
답글
접근이 BFS같아 보이는데 순간이동은 점수가 0이니까, 순간이동 전까지의 점수를 미리 캐싱해뒀다 순간이동 이후의 인접 노드를 탐사할 때 가져와서 쓰면 되겠지

익명(27.35) 2021-09-16 08:31
답글
물론 여기서 모든 점수에 대한 인접 노드들을 깔 필요는 없고 갈 수 있는 이전 점수들에 대해서만 BFS를 수행한다면 훨씬 시간복잡도를 줄일 수 있을 거 같음

익명(27.35) 2021-09-16 09:03
답글
아 시간 엄청 줄였는데 그래도 몇 개 tle 뜨네

익명(210.91) 2021-09-16 09:40
답글
https://gall.dcinside.com/mgallery/board/view/?id=ps&no=15881&page=1

익명(27.35) 2021-09-16 09:47
답글
오르가즘 똥꼬쇼하다 풀었어 시간내줘서 감사ㅋㅋ

익명(210.91) 2021-09-16 09:53

댓글 8