Multi-Source BFS 도입을 통한 시간 복잡도 O((M×N)²)에서 O(M×N)으로 최적화

Context

그리드 내 여러 지점에서 동시에 확산되는 상태 변화를 추적해야 하는 문제 상황. 전체 그리드를 반복 스캔하는 Brute Force 방식은 중복 방문으로 인한 높은 시간 복잡도 발생.

Technical Solution

• 초기 상태의 모든 Rotten Orange를 Queue에 동시 삽입하는 Multi-Source BFS 구조 설계
• 각 BFS Level을 시간 단위(1분)로 매핑하여 최단 시간 도달 보장
• 4방향 탐색 및 방문 여부 확인을 통한 중복 연산 제거
• Fresh Orange 카운트를 통한 최종 도달 가능 여부 검증 로직 구현
• Queue 기반의 Level-order Traversal을 통한 동시 확산 프로세스 시뮬레이션

Impact

• Time Complexity: O((M × N)²) → O(M × N)으로 개선
• Space Complexity: O(1) → O(M × N)으로 변경하며 연산 효율성 확보