2206번 - 벽 부수고 이동하기
벽을 한번만 부술수 있으니까 쉽게 생각해서 벽을 한개씩 부순다음에 bfs 돌려봤거등요?
이러면 당연히 시간초과가 날수밖에 없는건가요?
5 80100000001010000010100000101001100010010
이 테스트 케이스 때문에 제대로 못풀겠네요...ㅠ
벽을 하나씩 부숴보고 진행하는 알고리즘의 시간복잡도를 생각해 보면,
부숴봐야 할 벽의 개수 : 최대 O(NM)
BFS 한 번에 필요한 시간 : O(NM)
-> 총 시간복잡도 O(N^2M^2) ~ 10^12
1초에 대략 10^8번 정도의 연산을 수행할 수 있으니까, 이 풀이는 확실히 TLE가 날 것 같넨요.
이 문제는 BFS 한 번만 수행해도 풀 수 있는 문제입니다.
좀 더 생각해 보세요!
댓글을 작성하려면 로그인해야 합니다.
dhedaa 6년 전
벽을 한번만 부술수 있으니까 쉽게 생각해서 벽을 한개씩 부순다음에 bfs 돌려봤거등요?
이러면 당연히 시간초과가 날수밖에 없는건가요?
5 8
01000000
01010000
01010000
01010011
00010010
이 테스트 케이스 때문에 제대로 못풀겠네요...ㅠ