qw2er   2년 전

아래와 같은 알고리즘(BFS)을 사용하였는데 시간 초과가 발생하였습니다. 

1. 토마토가 새로 익은 경우 리스트에 집어넣고 안 익은 토마토가 존재하는지 검사하였습니다. 

2. 토마토가 모두 익은 경우 걸린 날짜를 반환합니다. 

3. 1에서 리스트에 넣은 토마토의 주변 토마토를 익었다고 표시합니다. 

4. 주변 토마토가 한 개라도 새로 익은 경우 위의 작업을 반복합니다. 

5. 3번 과정(주변 토마토를 익었다고 표시하는 과정)에서 새로 익은 토마토가 없는 경우 -1로 막혀 영원히 안 익는 토마토가 있다는 뜻이므로 -1을 반환합니다. 

시간을 줄일 수 있는 불필요한 과정이나 구현한 알고리즘 중 틀린 부분을 알려주시면 감사하겠습니다.

djm03178   2년 전

이 알고리즘의 수행 시간을 생각해봅시다.

매 사이클마다 n*m 크기의 배열을 모두 돌면서 새로 익은 토마토들에 대해서 검사를 수행하는군요.
새로 익은 토마토들에 대해서 검사하는 횟수는 어차피 창고의 크기를 넘어가지 않으니, O(nm)으로 문제될 수준이 아닙니다.
그러나, n*m 크기의 배열을 검사하는 횟수가 가장 많은 경우는 마치 소용돌이 모양으로 돌면서 한 줄로만 토마토가 익어나갈 수 있는 상황 같은 걸 생각하면 되는데, 이 경우에는 돌아야 하는 사이클의 횟수가 무려 O(nm)에 육박하고, 매 사이클에 n*m개를 검사해야 하니 시간복잡도는 O(n2m2)이 됩니다.

어떻게 줄여야 할까요? 핵심은, "이전 사이클에 찾은 '새로 익은 토마토'에 대한 정보를 다음 사이클에서 바로 사용한다"입니다. 배열을 일일히 순회할 필요가 없습니다. 어디어디에 새로 익은 토마토가 있는지에 대한 정보를 알고 있으면 됩니다.

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