[Python] 삼성 sw 역량 테스트 기출 - 미세먼지 안녕!

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

[ 알고리즘 ]

시뮬레이션

 

[문제 접근]

문제에 제시된대로 미세먼지 확산과, 공기청정기 작동을 구현하는 문제이다.

문제대로 구현하는건 어렵지 않았는데..

시간초과 문제가 발생하여 애를 먹었던 문제이다.

 

1) 5이상인 경우에만 미세먼지가 퍼지는 조건도 추가해보았고

2) deepcopy로 기존의 graph를 저장하는 방식대신 빈 리스트에 확산되는 미세먼지의 양을 저장하여 마지막에 이중 for문으로 더해주는 방식 (대부분의 사람들이 이 방식으로 해결한듯) 으로도 시도해보았는데..

계속 시간 초과가 뜬다..?

그래서 pypy3로 제출하였더니 다행히 통과는 떴다.

근데 아직도 뭐가 문제인지 모르겠다는게 문제다..ㅎㅎ 해결방법을 알면 댓글을 남겨주세요,,

 

[코드] -pypy3으로 제출

# 확산 -> 공기 청정기 작동
from collections import deque
import copy
import sys

dx=[-1,1,0,0]
dy=[0,0,-1,1]

R,C,T=map(int,sys.stdin.readline().strip().split())
graph=[]
answer=0
a=-1

for _ in range(R):
    graph.append(list(map(int,sys.stdin.readline().strip().split())))

# 미세 먼지가 있는 곳, 공기 청정기가 있는 곳 확인

# 미세먼지 = (a,0) & (a+1,0)
# 청소기 위치 구하기
for i in range(R):
    for j in range(C):
        if graph[i][j] == -1:
            a = i
            break
    if a!=-1:
        break

b=a+1

for _ in range(T):
    new_graph = copy.deepcopy(graph)  # 원본 데이터 값을 참조할 데이터
    que=deque()

    # 미세먼지 있는 부분 구하기
    for i in range(R):
        for j in range(C):
            if graph[i][j] != -1 and graph[i][j] != 0:
                que.append((i, j))  # 미세 먼지 있는 곳 저장


    # 확산
    while que:
        x,y=que.popleft() # 미세먼지 위치
        cnt=0

        for i in range(4):
            xx=dx[i]
            yy=dy[i]

            if xx+x<0 or xx+x>=R or yy+y<0 or yy+y>=C:
                continue
            if new_graph[xx+x][yy+y]!=-1:
                graph[xx+x][yy+y]+=(new_graph[x][y])//5
                cnt+=1

        graph[x][y]-= ((new_graph[x][y])//5)*cnt

    # 공기 청정기 작동
    # 위쪽부터 작동
    # 공기청정기 바로 위에는 사라짐
    graph[a-1][0]=0

    for i in range(a-2,-1,-1):
        graph[i+1][0]=graph[i][0] # 맨 왼쪽
        graph[i][0]=0

    for i in range(1,C):
        graph[0][i-1]=graph[0][i] # 맨 위 중간
        graph[0][i]=0

    for i in range(1,a+1):
        graph[i-1][C-1]=graph[i][C-1] # 맨 오른 쪽
        graph[i][C-1]=0

    for i in range(C-2,0,-1):
        graph[a][i+1]=graph[a][i] # 맨 아래
        graph[a][i]=0

    # 아래쪽 작동
    # 공기 청정기 바로 아래는 사라짐
    graph[b+1][0]=0

    # 맨 왼쪽
    for i in range(b+2,R):
        graph[i-1][0]=graph[i][0]
        graph[i][0]=0

    # 맨 아래쪽
    for i in range(1,C):
        graph[R-1][i-1]=graph[R-1][i]
        graph[R-1][i]=0

    # 맨 오른쪽
    for i in range(R-2,b-1,-1): 
        graph[i+1][C-1]=graph[i][C-1]
        graph[i][C-1]=0

    # 맨 위쪽
    for i in range(C-2,0,-1):
        graph[b][i+1]=graph[b][i]
        graph[b][i]=0


for List in graph:
    answer+=sum(List)

print(answer+2)