29. infection spread [12 1주차]

29. Infection Spread [12-1주차]

2024년 1월 14일 일요일

오후 2:45

<Event Queue를 이용한 Infection Spread 문제>

mxn 격자 칸에 감염된 칸이 존재한다. 어떤 칸의 상하좌우 4칸 중 두 칸 이상이 감염되어 있으면, 그 칸도 감염된다. 감염이 전부 끝난 뒤, 어떤 칸이 감염되어 있는가?

전체 칸을 확인하면서 처음으로 감염이 옮을 칸을 event queue에 넣는다. queue에서 하나를 꺼내 감염을 시킨다. 그리고 상하좌우 칸에 감염될 칸이 있는지 확인한다. 감염될 칸이 있으면 그 칸을 event queue에 넣는다. event queue가 빌 때까지 반복한다.

처음에 모든 칸을 한번 분석하고, 큐에 들어갔다 나오는 칸의 개수가 최대 m*n개 이므로

O(m*n)

이 걸린다.