cokcjswo   1달 전

제가한 방식은


얼음이 아무리 많아도 시간이 3000초 이내에 모든 얼음이 다 녹으니까 (1500*1.414...)


시간 0부터 3000까지 loop 돌렸습니다...

매 loop 마다 BFS 돌렸구요... 

이게 아무생각없이 짜면 시간복잡도가 3000 * 1500*1500이니까 (1500*1500은 개별 BFS 시간복잡도)

70억 정도 되길래

시작점과 목적점이 있는 것을 이용해서 양방향 탐색까지 이용해줬는데... 어떻게 시간을 더 줄일 수 있을까요?

매 시간마다 melt 함수에서 물과 이웃한 얼음들은 다 녹여줬구요...


ㅠㅠㅠㅠㅠㅠㅠㅠ


BOJ 3055 탈출 문제 처럼 풀려고 그랬는데...


정답률은 더 높아도 이게 훨씬 어려운 문제같네요....


코드는 보기 편하시라고 solve 부분만 올립니다...



zlzmsrhak   1달 전

0. 코드는 전체를 올려주세요. 코드가 부분만 있으면 실행을 시켜볼 수가 없어서 더 불편합니다.

1. 저기서 시간을 더 줄이기 위해서는 단순히 BFS를 구현하는 것 이상의 생각을 해야 합니다.

모든 칸의 빙하가 없어지는 시간을 1500*1500에 계산할 수 있고, 이 정보를 이용하여 두 백조가 물로 연결되는 최소 시간을 구할 수 있습니다.

cokcjswo   1달 전

네 감사합니다. 고민해보겠습니다. 코드 전문은 여기 있습니다.

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