<baekjoon> 미세먼지 안녕

풀이

미세먼지가 존재하는 칸은 매 초마다 동시에 확산하므로 처음 확산할때는 boolean배열을 이용하여 true인 공간만을 확산하였다. 그 이후부터는 모든 칸을 true로 설정하여 확산을 실시하였다.

여기서 중요한 것은 확산 시, 인접한 칸에 미세먼지가 존재하면 바로 새로 확산된 값으로 변경해주면 안된다.

변경전 값이랑 후 값을 따로 보관한후에 제일 마지막에 값을 변경하여야 한다. 아니면 틀린 계산이 나온다.

 

공기청전기는 dfs알고리즘을 사용하여 새로운 값을 옆칸에 적용하기전에 새로운 dfs로 타고 들어가 마지막에 더이상 진행할 수 없는칸이면(진공청소기가 존재하는 칸) dfs를 return해주면서 값을 변경하였다.

 

코드