[BOJ][17144] 미세먼지 안녕!

문제 : www.acmicpc.net/problem/17144

---

구현문제.

 

먼지가 이동한 뒤의 모습을 저장할 배열 (let, newArr)을 하나 만든다. newArr은 0으로 초기화한다.

 

먼저 먼지의 확산된 모습을 newArr 배열에 담는다.

집 배열을 탐색하면서 해당 칸(let, (x,y))의 값이

   -1 이면 공기청정기 이므로 나중에 공기청정기 확산할 때를 대비해 해당 좌표를 cleaners 배열에 담아두고 다음을 탐색한다.

   0 이면 먼지가 없다는 뜻이므로 다음을 탐색한다

   양수값이면 먼지가 확산시킨다. 상하좌우로 이동한 좌표값을 (nx, ny)라 하자. (nx, ny)가 RxC 배열칸을 넘어가지 않고 집에서 nx, ny 좌표값이 -1이 아닌경우(공기청정기) 해당 칸으로 먼지가 확산될 수 있으므로 newArr[nx][ny]에 탐색중인 칸의 먼지 양 / 5를 더해준다. 이 때, 이미 다른 먼지의 확산으로 newArr[nx][ny]에 먼지가 이미 있을 수 있으므로 덮어쓰기하면 안되고 더해줘야한다. newArr[x][y]에는 기존 먼지 양에 확산된 먼지 양을 뺀 값을 더해준다.

 

먼지의 확산이 끝났으면 공기청정기(cleaners)에 의해먼지를 이동시킨다.

이동시키고자 하는 칸의 좌표 (x, y), 방향을 변수로 두고 먼지를 이동시킨다.

이동시키고자 하는 다음 좌표(nx, ny)가

   공기청정기(-1)인 경우 이동을 종료한다.

   칸을 벗어나는 경우 방향을 변경한다. (시계방향 : 오른쪽 -> 아래 -> 왼쪽 -> 위 / 시계반대방향 : 오른쪽 -> 위 -> 왼쪽 -> 아래)

 

이를 T 번 반복하고 난 뒤의 집 칸의 먼지 총 양을 구하면 정답이된다.

 

시간복잡도는 O(RCT).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/BOJ/17144.%EB%AF%B8%EC%84%B8%EB%A8%BC%EC%A7%80%20%EC%95%88%EB%85%95!.cpp

---

구현문제는 코드를 보는게 더 이해가 잘되기 때문에 코드 참조를 권한다.