trevor0513   2년 전

안녕하세요. 원숭이가 말이 되고싶은 문제를 풀다가 시간초과가 발생해서 질문 올립니다 ㅠㅠ...

50%에서 시간 초과가 발생하는데 이것보다 더 최적화 할 수 있는 방안이 생각이 안나네요. 현명하신분들의 조언을 좀 듣고싶습니다..

대부분의 코드는 읽기 쉬울것같습니다만,

cnt는 이동 횟수를 의미하며,

visited는 방문여부를 저장하는데 기본적으로 방문하지 않았으면 -1을 저장하고있고

방문을 했으면 남은 K값이 저장되어있습니다.

지금 온 위치에서 더 많은 K로 이 곳을 통과한 과거 경험이 있으면 queue에 추가하는건 의미가 없어서 추가하지 않습니다.

우선순위 큐를 이용해서 cnt가 적은 순서대로 pop합니다.

고수님들 더 최적화를 할 수 있는 방법좀 알려주세요 ㅠㅠ

jh05013   2년 전

python과 똑같은데 훨씬 빠른 pypy로 제출해 보세요.

가까스로 통과는 되지만, 몇 가지 비효율적인 부분이 있습니다. [0, [0, 0, K]]보다 tuple (0, 0, 0, K)가 더 가벼울 것이고, 다익스트라 알고리즘 말고 BFS로 더 빠르게 풀 수 있습니다.

trevor0513   2년 전

jh05013 님 감사합니다 ㅠㅠ pypy3로 제출하니까 통과하네요.

다른 방법으로도 풀어볼게요!

댓글을 작성하려면 로그인해야 합니다.