leejaengjaeng   7년 전

다익스트라 기본문제인거 같아서 우선순위큐 사용해서 풀었는데 채점 4퍼센트에서 시간초과나네요

케이스는 잘 맞는거 같은데

혹시 입력받는거 문제일까요

zlzmsrhak   7년 전

우선순위 큐를 사용할 때는, pop을 할 때마다 visited 배열을 확인해보아야 합니다.

같은 정점이 여러 번 우선순위 큐에 push될 수 있는데, 이것을 처리해주지 않으면 쓸모없는 연산량이 매우 많아져 시간초과가 날 수 있습니다.

leejaengjaeng   7년 전

50번 줄 위에 

if(visited[currentP]) continue;

이거 한줄 추가했는데 이번엔 답이 틀렸네요 ㅎㅎ.. 뭐가 틀린거지..

zlzmsrhak   7년 전

입력 데이터 중 버스 비용이 0인 경우가 있는 것 같습니다.

leejaengjaeng   7년 전

갓.. 

감사합니다 

그런데 이번엔 런타임 에러 나네요 

큐에 너무 값이 많이 들어가나 해서 

다익스트라 부분을 큐 안쓰고 아래처럼 반복문으로 고쳤는데도 런타임 에러가 납니다. 

이유가 뭘까요...




zlzmsrhak   7년 전

다익스트라 부분에는 문제가 없어보이는데 전체 코드를 보는 것이 좋을 거 같아요.

leejaengjaeng   7년 전

selectedPoint를 -1로 초기화 하고 반복횟수가 문제 였는데 수정해도 또 런타임 에러 나네요.. 

ㅠㅠ

leejaengjaeng   7년 전

다익스트라 부분말고 전체 코드에 초기화랑 값 입력받는거 밖에 없어요 ㅠㅠ  

10몇% 까지는 가는거보면 입력 함수 문제도 아닐것같고.. 

zlzmsrhak   7년 전

1. 40번째 줄 nextLine()때문에 입력이 잘못 받아지는 것 같습니다.

2. 가중치 0인 간선이 입력으로 들어올 때 35~39번째 줄에서 0을 다른 값으로 바꿀 수 있습니다.

3. 무슨 이유에서인지 모르겠지만 package baekjoon; 때문에 틀리는 것 같습니다.

leejaengjaeng   7년 전

nextInt()랑 nextLine()이 문제 였네요... 

입력받는 방법을 바꿔서 해결했습니다!

갓 zlzmsrhak 님 정말 감사합니다 

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