kjho1037   2년 전

좀 무식하식 하지만..

모든 벽 없애가면서 최단경로 찾아서 그 중에서 최소값 출력하는건데...

진짜 72퍼 정도에서 계속 런타임에러떠서 미치겠습니다ㅜ,ㅠ

djm03178   2년 전

92번째 줄을 return 0; 으로 바꿔주면 맞습니다.

그런데 이 코드가 통과되는 걸 보니 아직 데이터가 약하군요. 데이터 추가 요청을 해야겠습니다.

kjho1037   2년 전

답변 감사합니다.

처음에 BFS로 풀었는데...계속 시간 초과가 나더군요!!!! 생각해보니 1000*1000*1000*1000 의 시간 복잡도가 나오는 것 같은데 맞나요???

djm03178   2년 전

여러 가지 제약 조건 때문에 최악의 경우에도 약 1/4 정도 되긴 하지만, 기본적으로는 O(N^2*M^2)이 맞습니다.

kjho1037   2년 전

한 가지 궁금한게 있는데!! 제가 처음에 BFS로 할때는 시간초과가 났는데, 백트랙킹을 쓰니까 시간초과가 안 나더라구요....최단거리를 구할 때 백트랙킹이 더 좋은가요???

djm03178   2년 전

BFS로 시간 초과가 났다면 BFS를 잘못 짜신 겁니다. 제가 코드를 잘못 봤는데, 이건 O(N^2*M^2)이 아니라 지수복잡도네요. 아래와 같은 케이스만 넣어도 아주 아주 오랜 시간이 걸립니다.

그리고 최단 거리는 무조건 BFS입니다. 다음 글을 읽어보세요. https://www.acmicpc.net/board/...

그리고 질문을 올릴 때 위에 읽으라고 나오는 공지사항도 꼭 읽어보시기 바랍니다.

kjho1037   2년 전

답변 감사합니다.

아래는 같은 방식으로 BFS로 실행한 것인데..

아무리 생각해도 BFS로 짠 것이 시간초과가 날 리가 없는데 계속납니다.

주변에 딱히 물어볼 사람도 없고해서ㅜ,ㅠ하루종일 고민해도 위에 코드는 통과하는데 아래 코드는 시간초과나는 이유를 모르겠습니다ㅜ,ㅠ

djm03178   2년 전

BFS는 큐에 넣을 때 방문했다는 표시를 해야 됩니다. 큐에서 뺀 다음에 하면 늦습니다. 여러 방향에서 어떤 칸으로 동시에 옮겨가려고 하면 무슨 일이 발생할까요?

위에 드린 케이스만 넣어봐도 큐의 크기를 한참 넘어가버리게 됩니다.

kjho1037   2년 전

답변 감사합니다!!!!

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