[백준/17144/파이썬] 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

Problem

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다.

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

조건

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

 

SOL

 

쉽지않았던 시뮬레이션 문제이다.  처음 풀때는, board를 복사해서, 다시 board에 붙여넣는 방식으로 구현했고, 시계방향/반시계방향으로 도는걸 구현하긴 했는데, 상당히 주먹구구식으로 구현을 했었다.

순서도

1. air_cleaner의 위치를 찾아준다.
   • for문 1개면 간단하게 구현할 수 있다. 공기청정기는 크기가 2이므로, head부분만 찾으면, tail부분은 바로 아래에 있다.
2. 먼지를 퍼뜨리는 함수를 만들어준다.
   • 처음 구현해줄 때는, board를 복사해서,  복사해준 board에서 작업을 하고 , 다시 붙여주는 방식으로 구현했는다. *개선 ) 굳이 복사할 필요없이, 임시 board를 만들어준뒤, board에 반영해야할 크기변화를 모두 기록한뒤, board에 그대로 합쳐주는 방식으로 변경했다. 메모리공간이랑, 코드 가독성, 시간을 좀 save 했다.
3. aircleaner가 동작하는 함수를 만들어준다.
   • aircleaner가 동작하는 방식은 반시계,시계방향으로 회전하는건데, 반시계/시계방향으로 배열을 회전시키는 방법은 여러가지 방법이 있지만, 여기서는 while True를 이용해서, 시작점에 다시 좌표가 돌아오면 반복을 끝내는 형식으로 구현했다. 이때, 전에 있던 값을 저장하는 변수를 선언해서, 값을 한칸씩 밀어주는 방식으로 구현했음!

import sys
from collections import deque
from copy import deepcopy
input= sys.stdin.readline

dx=[0,1,0,-1]
dy=[1,0,-1,0]
N,M,tc = map(int,input().split())
board=[list(map(int,input().split())) for _ in range(N)]

for i in range(N):
    if board[i][0] == -1:
        up = i
        down = i + 1
        break

def spread_dust(tmp_board):
    dq=deque()
    for y in range(N):
        for x in range(M):
            if board[y][x] >0:
                dq.append((y,x))
    dq_len=len(dq)
    for _ in range(dq_len):
        y,x=dq.popleft()
        cnt=0
        s_dust=board[y][x]//5
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if not (0<=ny<N and 0<=nx<M):
                continue
            if board[ny][nx] == -1:
                continue
            cnt+=1
            tmp_board[ny][nx] +=s_dust
        tmp_board[y][x] =tmp_board[y][x]-(s_dust)*cnt
    return tmp_board
def aircon():
    # 위쪽
    air_y_dir=[0,-1,0,1]
    air_x_dir=[1,0,-1,0]
    dir=0
    before=0
    y,x=up,1
    while True:
        ny=y+air_y_dir[dir]
        nx=x+air_x_dir[dir]
        if y==up and x==0:
            break
        if not (0<=ny<N and 0<=nx<M):
            dir += 1
            continue
        board[y][x] ,before=before,board[y][x]
        y=ny
        x=nx
    #아래쪽
    air_y_dir = [0, 1, 0, -1]
    air_x_dir = [1, 0, -1, 0]
    direct = 0
    before = 0
    y, x = down, 1
    while True:
        ny = y+air_y_dir[direct]
        nx = x +air_x_dir[direct]
        if y == down and x == 0:
            break
        if not (0<=ny<N and 0<=nx<M):
            direct += 1
            continue
        board[y][x], before = before, board[y][x]
        y=ny
        x=nx
while tc:
    tmp_board=deepcopy(board)
    board=spread_dust(tmp_board)
    aircon()
    tc-=1
answer=0
for i in range(N):
    for j in range(M):
        if board[i][j] > 0:
            answer += board[i][j]

print(answer)

 

여러 블로그들을 참고해서, 코드의 가독성을 높이고, 필요없는 작업은 빼주는 형식으로 , 다시 코딩을 해보았음!

#미세먼지 안녕!
import sys
input= sys.stdin.readline

N,M,tc=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(N)]

#find air_cleaner
airhead=-1
airtail=-1
for i in range(N):
    if board[i][0]==-1:
        airhead=i
        airtail=i+1
        break

def spread_dust():
    #update data를 기록하는 board
    update_board=[[0 for _ in range(M)] for _ in range(N)]
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    for i in range(N):
        for j in range(M):
            if board[i][j] >0:
                total=0
                dust=board[i][j]//5
                for k in range(4):
                    ny=i+dy[k]
                    nx=j+dx[k]
                    if not (0<=ny<N and 0<=nx<M):
                        continue
                    if board[ny][nx]== -1:
                        continue
                    update_board[ny][nx] = update_board[ny][nx]+dust
                    total+=dust
                board[i][j] -=total
    #Update board
    for i in range(N):
        for j in range(M):
            board[i][j] +=update_board[i][j]
    #print(board)

def air_cleaner():
    #head
    dx=[1,0,-1,0]
    dy=[0,-1,0,1]
    dir=0
    before=0
    y,x=airhead,1
    while True:
        ny=y+dy[dir]
        nx=x+dx[dir]
        if y== airhead and x==0:
            break
        if not (0<=ny<N and 0<=nx<M):
            dir+=1
            continue
        board[y][x],before = before,board[y][x]
        #print(f"y:{y},x:{x},dir:{dir}")
        y=ny
        x=nx
    #tail
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    dir=0
    before =0
    y,x= airtail,1
    while True:
        ny=y+dy[dir]
        nx=x+dx[dir]
        if y==airtail and x==0:
            break
        if not (0<=ny<N and 0<=nx<M):
            dir+=1
            continue
        board[y][x] , before =before,board[y][x]
        y=ny
        x=nx

for _ in range(tc):
    spread_dust()
    air_cleaner()
ans=0
for i in range(N):
    for j in range(M):
        if board[i][j] >0:
            ans +=board[i][j]

print(ans)