[백준] 17144 미세먼지 안녕!

문제

• RxC 격자판 위에 공기청정기를 설치하고 T초 지난 뒤 방에 남아있는 미세먼지 양 구하기
  • 6 <= R, C <= 50
  • 1 <= T <= 1000
• 공기청정기는 항상 1열에 설치되고, 크기는 두 행을 차지한다.
• 공기청정기가 없는 칸에는 $A_{r,c}$ 만큼의 미세먼지가 있다.
• 1초 동안 아래 적힌 일이 순서대로 일어난다.
  • 1) 미세먼지 확산
    • 미세먼지가 인접한 네 방향으로 확산 (공기청정기 칸 제외) 
    • 소수점 제외 $A_{r,c}$/5 만큼 확산되고, 해당 칸에 확산된 만큼 미세먼지 양이 줄어든다.
  • 2) 공기청정기 작동
    • 공기청정기 위쪽 바람은 반시계 방향으로 순환하고, 아래쪽 바람은 시계 방향으로 순환
    • 바람이 불면 미세먼지가 바람 방향대로 한 칸씩 이동
    • 공기청정기로 들어간 미세먼지는 모두 정화 됨

 

풀이

• 구현 문제 
• 세 단계가 있다.
  • 1) 미세먼지 확산 단계
    • 전체 맵을 돌면서 미세먼지가 존재하는 경우, 4가지 인접 방향으로 퍼뜨리기
    • 주의 : 공기청정기가 있거나, 맵 바깥으로는 퍼뜨릴 수 없다.
  • 2) 공기청정기 위쪽 바람
    • 바람 방향을 거슬러서 왼쪽 - 위 - 오른쪽 - 아래 순서로 이전 칸의 먼지를 다음 칸 먼저로 이동
    • 공기청정기 다음의 첫 칸은 0으로 채운다.
  • 3) 공기청정기 아래 바람
• 2차원 리스트 복사할 때 deepcopy 말고 리스트 슬라이싱을 하면 시간 단축된다.
• 근데 pypy 로만 통과한다.. 

 

R, C, T = map(int, input().split())
maps = []   # 전체 맵
robot = []  # 공기청정기 행 위치
for i in range(R):
    maps.append(list(map(int, input().split())))
    if maps[i][0] == -1:    # 공기청정기 행 위치 기록 
        robot.append(i)

# T초 동안 반복
for _ in range(T):
    # 1. 미세먼지 확산
    tmp = [row[:] for row in maps]
    for x in range(R):
        for y in range(C):
            dust = tmp[x][y]
            if dust > 0 :     # 미세먼지가 있는 경우
                for (nx, ny) in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
                    # 이동 가능하고, 공기청정기가 아닌 칸일 때
                    if 0 <= nx < R and 0 <= ny < C and maps[nx][ny] != -1:
                        maps[nx][ny] += dust // 5
                        maps[x][y] -= dust // 5

    # 2. 공기청정기 작동
    # up cycle
    for i in range(robot[0]-1, 0, -1):      # left
        maps[i][0] = maps[i-1][0]
    for i in range(C-1):                    # up
        maps[0][i] = maps[0][i+1]
    for i in range(robot[0]):               # right
        maps[i][C-1] = maps[i+1][C-1]
    for i in range(C-1, 1, -1):             # down
        maps[robot[0]][i] = maps[robot[0]][i-1]
    maps[robot[0]][1] = 0   # 맨 첫 칸 0으로

    # down cycle
    for i in range(robot[1]+1, R-1):        # left
        maps[i][0] = maps[i+1][0]
    for i in range(C-1):                    # down
        maps[R-1][i] = maps[R-1][i+1]
    for i in range(R-1, robot[1], -1):      # right
        maps[i][C-1] = maps[i-1][C-1]
    for i in range(C-1, 1, -1):             # up
        maps[robot[1]][i] = maps[robot[1]][i-1]
    maps[robot[1]][1] = 0

answer = 2      # 공기청정기 2칸 -1 이므로
for row in maps:
    answer += sum(row)
print(answer)

 

References

• 백준 17144번
• 2023.04.27 오늘의 문제