dhedaa   4년 전

벽을 한번만 부술수 있으니까 쉽게 생각해서 벽을 한개씩 부순다음에 bfs 돌려봤거등요?

이러면 당연히 시간초과가 날수밖에 없는건가요?


5 8
01000000
01010000
01010000
01010011
00010010

이 테스트 케이스 때문에 제대로 못풀겠네요...ㅠ


dotorya   4년 전

벽을 하나씩 부숴보고 진행하는 알고리즘의 시간복잡도를 생각해 보면,

부숴봐야 할 벽의 개수 : 최대 O(NM)

BFS 한 번에 필요한 시간 : O(NM)

-> 총 시간복잡도 O(N^2M^2) ~ 10^12


1초에 대략 10^8번 정도의 연산을 수행할 수 있으니까, 이 풀이는 확실히 TLE가 날 것 같넨요.


이 문제는 BFS 한 번만 수행해도 풀 수 있는 문제입니다.

좀 더 생각해 보세요!

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