[백준/Python] 17144번: 미세먼지 안녕!

📖  문제 링크

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

17144번: 미세먼지 안녕!

 

 

👩‍💻  문제풀이

 

오기로 푼 문제였다.....

구현 문제는 요구조건을 하나라도 놓치면 발견도 어렵고, 디버깅하느라 시간이 오래 걸려서 까다로운 것을 매번 느낀다.

 

그래도 모든 예제 케이스와 스몰케이스, 라지케이스를 전부 테스트한 후 제출해보았다. 

파이썬은 당연히 시간 초과가 났고...ㅎㅎ

심지어 PyPy3로 제출했는데도 2852ms라는 엄청난 시간이 걸렸다. 

 

그래서 대체 무엇이 문제인지 고민하다, 미세먼지 확산 과정에서 queue에 불필요한 입출력을 했단 걸 발견!!! 

해당 코드를 고쳤더니 832ms로 줄어든것을 확인할 수 있었다. 

 

참 깨달음을 많이 얻었던 문제.

좀 더 꼼꼼하고 빠르게 푸는 연습을 꾸준히 해보자!

 

 

 

✅  최종 코드

from collections import deque
from os import TMP_MAX
r, c, t = map(int, input().split())

board = [list(map(int, input().split())) for _ in range(r)]
robot = deque()
robot2 = deque()
for i in range(r):
    for j in range(c):
        if board[i][j] == -1:
            robot.append([i,j])
            robot2.append([i,j])      


def bfs(x, y):
        q = deque()
        cnt = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<r and 0<=ny<c and board[nx][ny] != -1:
                check[nx][ny] += (board[x][y] // 5)
                cnt += 1
                
        result = board[x][y] - ((board[x][y]//5)*cnt) 
        if result > 0:
            check[x][y]+=result
    

def upmove(dr, start, end):
    while True:
        x, y = robot.popleft()
        nx = x + ux[i]
        ny = y + uy[i]

        if start<=nx<end and 0<=ny<c:
            if board[x][y] == -1 or board[nx][ny] == 0:
                board[nx][ny] = 0
                robot.appendleft([nx, ny])
                continue
            elif board[nx][ny] == -1:
                board[x][y] = 0
                robot.appendleft([nx, ny])
                return
            else:
                board[x][y] = board[nx][ny]
                board[nx][ny] = 0
                robot.appendleft([nx, ny])
            
        else:
            robot.appendleft([x, y])
            return
  
        
def downmove(dr, start, end):
   
    while True:
        x, y = robot.pop()
        nx = x + ux[i]
        ny = y + uy[i]

        if start<=nx<end and 0<=ny<c:
            
            if board[x][y] == -1 or board[nx][ny] == 0:
                board[nx][ny] = 0
                robot.append([nx, ny])
                continue
            elif board[nx][ny] == -1:
                
                robot.append([nx, ny])
                return
            else:
                board[x][y] = board[nx][ny]
                board[nx][ny] = 0
                robot.append([nx, ny])
            
        else:
            robot.append([x, y])
            return
  
                


for k in range(t):                
    check = [[0]*c for _ in range(r)]
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    
    for i in range(r):
        for j in range(c):
            if board[i][j] != 0 and board[i][j] != -1:
                bfs(i, j)
                


    for i in range(r):
        for j in range(c):
            if board[i][j] != -1 and check[i][j] != 0:
                board[i][j] = check[i][j]
 
    #위쪽 공기청정기            

    ux = [-1, 0, 1, 0]
    uy = [0, 1, 0, -1]
    start = 0
    end = robot2[0][0] + 1
    for i in range(4):    
        upmove(i, start, end)


    #아래쪽 공기청정기    

    ux = [1, 0, -1, 0]
    uy = [0, 1, 0, -1]
    start = robot2[1][0]
    end = r
    for i in range(4):
        downmove(i, start, end)
    
        

answer = 0
for i in range(r):
    for j in range(c):
        if board[i][j] > 0:
            answer += board[i][j]
            
print(answer)