nill1024   4년 전

max를 여기서 100정도의 작은 수로 해주면 문제의 기본 테스트케이스(5, 17)가 정상적으로 2로 나오는데

max를 지금 되어있는것처럼 십만 정도의 큰 숫자로 하면 답이 3으로 나옵니다. 우선순위 큐상으로 t값이 낮을수록 먼저 뜨게 설정되어있는데..

이거 진심 맞왜틀입니다. 혹시 제 멍청한 실수를 지적해주실 분 없나요?

+ 제가 이 문제를 우선순위 큐로 풀기 전에 그냥 한 점을 방문할 시 그 점의 모든 *2^n 점에 대하여 바로 방문되도록 만드는 코드를 짰던 적이 있습니다. 그 코드가 시간초과가 나게 되어서 구글링하고 우선순위 큐를 사용한 코드로 바꾸긴 했는데 생각해보면 t의 우선순위 큐를 사용한 코드와 그 시간초과 코드의 논리 구조가 차이가 없는 것 같습니다. 어차피 우선순위 큐를 사용하면 t가 낮은것부터 나오게 되어 모든 *2^n점을 먼저 보게 되어있는데 대체 왜 차이가 나는거죠?(그 시간초과 코드는 밑에 주석으로 첨부했습니다.)

ps 고친 코드의 경우 제가 직접 구글링 해보고 짠건데 인터넷에 돌아다니는 돌리면 맞았습니다 나오는 코드랑 아무리 봐도 차이가 없습니다. 정말 이해가 안 되는데 도와주세요 ㅜㅜ

kyo20111   4년 전

틀리는 이유는 우선순위 큐에 넣자마자 visited에 체크를 해주어서 그렇습니다.

예를 들어 가야하는 곳이 28이라고 치고 우선순위 큐에 t=1,p=27와 t=1,p=14순서로 들어가 있다고 치면

먼저 t=1,p=27인 곳에 들어가 t=2,p=28을 우선순위 큐에 넣고 visited에 체크하게 되어 t=1,p=14순서때 visited[28]은 이미 체크되어 t=1,p=28을 우선순위 큐에 넣지 않을것 입니다.

kyo20111   4년 전

해결방안 2가지로 코드를 고쳐서 AC를 받았으니 궁금하시면 제 코드를 읽어보세요.

nill1024   4년 전

헉,,, 고쳐주시기까지 ㅜ 너무너무 감사합니다

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