grapecw   2년 전

일단, 첫번째 BFS 함수는 각 얼음이 녹는데 걸리는 시간을 리턴해 주는 함수입니다.

두번째 BFS 함수의 visited 배열은 각 위치마다 가는데 최소 필요한 시간을 저장하는 함수입니다.

즉, 한 백조의 위치에서 다른 백조의 위치까지 갈 수 있으면 그게 필요한 최소 시간이라고 생각했습니다.

그런데, 아무리 해도 시간 초과가 뜨더군요. 그래서 우선순위 큐가 아닌 그냥 큐를 통해 찾아보기도 했고, 아예 시간을 고정 시켜 놓은 다음에 바이너리 서치를 통해 최소 시간을 찾아보기도 했는데, 전부 시간 초과가 뜨더군요.

혹시, 이 시간 초과를 어떻게 해결 할 수 있는지 조언을 해주실 수 있으십니가?

kimjangh94   2년 전

언어가 다르지만 방법은 같을 거라고 생각하고 댓글 남겨봅니다.

저도 시간 초과에 걸렸었습니다.

모든 좌표를 돌며 빙하를 녹이기 위해 BFS를 하고, 백조를 찾기 위해 BFS를 했습니다.  이렇게 하면 시간 초과가 나오게 됩니다.

이 문제를 해결 하기 위해 각각 두 개의 큐를 두었습니다.

현재 물 상태인 큐, 다음 턴에 물이 될 좌표를 담는 큐

현재 물 상태에서 BFS를 돌며 X(빙하)를 만나게 되면 다음 턴에 물이 될 좌표를 담는 큐에 담습니다.

1초가 지나면

다음 턴에 물이 될 좌표를 담는 큐에서 -> 현재 물 상태인 큐로 좌표를 모두 옮긴 후 BFS를 반복합니다.

백조를 찾기 위한 방법도 동일하게 큐를 2개 사용함으로써 시간을 줄일 수 있습니다.

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