[백준(BOJ)] #17144- 미세먼지 안녕! (파이썬, PyPy3)

문제

 

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

17144번: 미세먼지 안녕!

 

---

문제 풀이

 

우선 이 문제는 구현 문제로 문제 이해를 이해하고, 문제를 어떻게 코드로 작성할 수 있는지를 확인하는 것으로 느껴졌습니다. 조건을 조금이라도 놓치고 문제를 풀게 되면, 원치 않은 결과를 얻을 수 있으므로 문제를 꼼꼼하게 읽어보는 것이 필수입니다!

 

미세먼지 확산 과정

미세먼지의 확산은 미세먼지가 있는 모든 칸에서 동시에 일어나기 때문에 2차원 리스트를 순차적으로 돌면서 무턱대고 확산을 적용하면 안 됩니다.

그러면 위와 같이 (0,1) 자리에 있는 미세먼지 값 30이 확산되면서 오른쪽에 있는 (0,2) 미세먼지에 영향을 끼치고 이 자리에 있는 값은 더해진 값으로 확산이 되기 때문입니다. 따라서 먼저 미세먼지가 있는 자리들을 현재 값과 같이 리스트에 저장을 하고, 그 리스트를 순차적으로 돌면서 확산을 시켜줍니다. 이때 확산 시킬 때는 영향받은 값은 확산할 때 제외시키기 위해서 저장했던 현재 값으로 확산을 시켜나가면 됩니다. 이 리스트를 순차적으로 돌면서 확산을 시켜주면 1초 동안의 확산은 마무리 됩니다.

 

 

공기청정기 작동 과정

 

공기청정기의 작동 과정은 바람이 위에서 나오는 위치 위 그림에서는 (2, 0), 아래에서 나오는 위치 (3, 0)을 기준으로 리스트를 위 그림과 같이 조정해줍니다. 위 그림은 1초 동안 공기청정기가 작동된 결과입니다.

 

---

구현

코드

import sys
input = sys.stdin.readline

# 미세먼지 상하좌우 확산
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 미세먼지 확산 함수
def inc(xx, yy, orgv):
    cnt = 0
    # 원래 값으로 확산하기 위해 값을 빼줌
    board[xx][yy] -= orgv
    for h in range(4):
        x = xx + dx[h]
        y = yy + dy[h]
        if 0 <= x < r and 0 <= y < c and board[x][y] != -1:
            cnt += 1
            board[x][y] += orgv // 5
    orgv -= (orgv // 5) * cnt
    # 확산시킨 다음 값을 다시 더해줌
    board[xx][yy] += orgv

# 공기청정기 위에서 나오는 바람으로 순환시키는 함수(반시계 방향)
def top_rot(s_i):
    for i in range(s_i-1, 0, -1):
        board[i][0] = board[i-1][0]

    board[0] = board[0][1:] + [0]

    for i in range(1, s_i+1):
        board[i-1][c-1] = board[i][c-1]

    board[s_i] = [-1, 0] + board[s_i][1:c-1]

# 공기청정기 아래에서 나오는 바람으로 순환시키는 함수(시계 방향)
def bottom_rot(s_i):
    for i in range(s_i + 1, r-1):
        board[i][0] = board[i+1][0]

    board[r-1] = board[r-1][1:] + [0]

    for i in range(r-1, s_i, -1):
        board[i][c-1] = board[i-1][c-1]

    board[s_i] = [-1, 0] + board[s_i][1:c-1]

if __name__ == "__main__":
    r, c, t = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(r)]
    d_list = list()
    top_s_pos = None
    bottom_s_pos = None

    # 공기청정기 위치
    for i in range(r):
        if board[i][0] == -1:
            top_s_row = i
            bottom_s_row = i+1
            break
    # t초 동안
    for _ in range(t):
        for i in range(r):
            for j in range(c):
            	# 미세먼지가 있는 위치를 값과 같이 저장
                if board[i][j] != 0 and board[i][j] != -1:
                    d_list.append((i, j, board[i][j]))

        # 확산
        for d in d_list:
            x, y, ov = d
            inc(x, y, ov)
        d_list.clear()
        # 공기청정기 작동
        top_rot(top_s_row)
        bottom_rot(bottom_s_row)
    cnt = 0
    # t초가 끝난뒤 미세먼지의 양
    for i in range(r):
        for j in range(c):
            if board[i][j] != 0 and board[i][j] != -1:
                cnt += board[i][j]
    print(cnt)

 

결과

---