백준 문제 중 17144번, 구현, ‘미세먼지 안녕!’

백준 문제 중 17144번

https://www.acmicpc.net/problem/17144

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

---

풀이

조건을 꼼꼼히 체크하는게 까다로웠던 문제이다.

처음 문제에 접근할때는 먼지가 여러 포인트에 존재하고 퍼지는 모양이 사방향으로 퍼져서 자연스럽게 BFS로 접근하려고 했었다. 하지만 문제를 점점 구체화시켜 가다보니, 확산하는 먼지끼리 서로 영향을 주면 안되기 때문에, BFS로 풀이하기는 제한됐다.
결국 브루트포스로 모든 동작을 구현했고, 너무 긴 코드에 중간중가 잦은 실수가 많이 생겼고 디버깅이 문제의 주가 되었던 문제이다.

코드의 구성은 다음과 같다.

1. 먼지가 있는 포인트를 체크할 check_dusts() 함수 선언
2. 먼지의 확산과 확산 가능한 지점을 세고, 가능한 지점에 따라서 1초간의 확산이 끝나고 난뒤의 상태를 최신화 해줄 함수 diffuse() 선언
3. 공기청정기를 기준으로 위 아래 반시계 방향과 시계 방향으로 최신화를 해줄 cleaner_work(cleaner_place) 함수 선언

함수의 구체적인 설명은 주석을 참고하자.

from pprint import pprint

R, C, T = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(R)]


cleaner_place = []
for i in range(R):
    for j in range(C):
        if room[i][j] == -1:
            cleaner_place.append(i)
            break

dr, dc = [1, 0, -1, 0], [0, 1, 0, -1]


def check_dusts():
    dusts = []
    for i in range(R):
        for j in range(C):
            if room[i][j] > 0:
                 # 먼지의 양이 0 이상이라면 먼지의 좌표와 양을 dusts에 저장
                dusts.append([i, j, room[i][j]])
    return dusts

def diffuse():
     # 확산의 정확한 동작을 위해서 새로운 배열 선언
    sub_room = [[0 for _ in range(C)] for _ in range(R)]
    dusts = check_dusts()
    
     # 각각의 먼지를 확산시키고 가능한 확산 지점을 세줌
    for r, c, amounts in dusts:
        possible = 0
        namounts = amounts//5
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i] 
            if 0 <= nr < R and 0 <= nc < C and namounts and room[nr][nc] != -1:
                sub_room[nr][nc] += namounts
                possible += 1

         # 확산이 일어난만큼 원래의 먼지양에서 감소 시켜줌
        room[r][c] -= possible * namounts

     # room에 1초간의 확산이 끝난뒤의 값인 sub_room을 더해줌
    for i in range(R):
        for j in range(C):
            room[i][j] += sub_room[i][j]
            
def cleaner_work(cleaner_place):
    c_upper, c_bottom = cleaner_place
     # 반시계 방향 회전
      # ↓
    for i in range(c_upper - 1, -1, -1):
        room[i + 1][0] = room[i][0]
     # 먼지 제거
    room[c_upper][0] = 0
      # ←
    for j in range(C-1):
        room[0][j] = room[0][j+1] 
      # ↑
    for i in range(c_upper):
        room[i][C-1] = room[i+1][C-1]
      # →  
    for j in range(C-2, -1, -1):
        room[c_upper][j+1] = room[c_upper][j]

     # 시계 방향 회전   
     # ↑
    for i in range(c_bottom, R - 1):
        room[i][0] = room[i + 1][0]
     # 먼지 제거
    room[c_bottom][0] = 0
     # ←
    for j in range(C - 1):
        room[R - 1][j] = room[R - 1][j + 1]
     # ↓  
    for i in range(R-2, c_bottom-1, -1):
        room[i+1][C-1] = room[i][C-1]
     # → 
    for j in range(C-2, -1, -1):
        room[c_bottom][j + 1] = room[c_bottom][j]

 # T초 동안 반복
for _ in range(T):
    pprint(room)
    diffuse()
    pprint(room)
    cleaner_work(cleaner_place)
    pprint(room)

ans = 0
for r in room: ans += sum(r)
print(ans)

7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
[[0, 0, 0, 0, 0, 0, 0, 9],
 [0, 0, 0, 0, 3, 0, 0, 8],
 [-1, 0, 5, 0, 0, 0, 22, 0],
 [-1, 8, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 10, 43, 0],
 [0, 0, 5, 0, 15, 0, 0, 0],
 [0, 0, 40, 0, 0, 0, 20, 0]]
[[0, 0, 0, 0, 0, 0, 1, 8],
 [0, 0, 1, 0, 3, 0, 5, 6],
 [-1, 2, 1, 1, 0, 4, 6, 5],
 [-1, 5, 2, 0, 0, 2, 12, 0],
 [0, 1, 1, 0, 5, 10, 13, 8],
 [0, 1, 9, 4, 3, 5, 12, 0],
 [0, 8, 17, 8, 3, 4, 8, 4]]
[[0, 0, 0, 0, 0, 1, 8, 6],
 [0, 0, 1, 0, 3, 0, 5, 5],
 [0, 0, 2, 1, 1, 0, 4, 6],
 [0, 0, 5, 2, 0, 0, 2, 12],
 [0, 1, 1, 0, 5, 10, 13, 0],
 [0, 1, 9, 4, 3, 5, 12, 8],
 [8, 17, 8, 3, 4, 8, 4, 0]]
188