[CLASS 4]백준 17144번 - 미세먼지 안녕!

17144번 - 미세먼지 안녕!

 

고통스러운 문제이다.

 

뭔가 삼성 역량테스트A 에서나 나올법한 구현 문제이다.

 

이런 문제는 문제 자체는 이해하기도 어렵지 않은데, 구현 그 자체가 힘들다.

 

처음에는 BFS로 해보려다가, 시프팅 되는 순간 큐에 있는 위치정보가 개판이 되기 때문에 그렇게 하지 않고 그냥 이중 for문으로 완전탐색 하면서 확산시키기로 했다.

 

내 코드(pypy3 제출):

# dawitblog.tistory.com/147
from sys import stdin
input = stdin.readline

R,C,T = map(int,input().split())
# 미세먼지 정보
mat = []
# 공기청정기 위치
cl = []
# 확산 방향
move = [(0,1),(0,-1),(1,0),(-1,0)]

for r in range(R):
    l = list(map(int,input().split()))
    if l[0] == -1:
        cl.append(r)
    mat.append(l)

u = cl[0]
d = cl[1]

for _ in range(T):
    temp = []
    for r in range(R):
        for c in range(C):
            if mat[r][c] != -1 and mat[r][c] > 4:
                # 확산 방향 count
                count = 0
                for dr,dc in move:
                    newR = r + dr
                    newC = c + dc

                    if 0<= newR < R and 0 <= newC < C and mat[newR][newC] != -1:
                        count += 1
                        temp.append((newR,newC,mat[r][c]//5))

                mat[r][c] -= (mat[r][c]//5)*count
    
    # 한꺼번에 확산값 적용
    for r,c,v in temp:
        mat[r][c] += v

    # shift
    for i in range(u-1,0,-1):
        mat[i][0] = mat[i-1][0]
    for i in range(d+1,R-1):
        mat[i][0] = mat[i+1][0]
    for i in range(C-1):
        mat[0][i] = mat[0][i+1]
        mat[-1][i] = mat[-1][i+1]
    for i in range(u):
        mat[i][-1] = mat[i+1][-1]
    for i in range(R-1,d,-1):
        mat[i][-1] = mat[i-1][-1]
    for i in range(C-1,0,-1):
        mat[u][i] = mat[u][i-1]
        mat[d][i] = mat[d][i-1]
    mat[u][1] = mat[d][1] = 0

# 출력
print(sum(sum(mat,[]))+2)

 

확산시킬때 주의할 점은 왼쪽->오른쪽, 위->아래 로 탐색을 진행하면서 확산시키기 때문에 만약 그때그때 확산한 값을 mat 에 반영한다면 아래에 이후에 이미 확산된 값으로 또 확산시킬수도 있기 때문에, 1초 내에 일어나는 확산은 한꺼번에 반영해야 한다.

 

그래서 temp 리스트를 만들고 거기다가 정보를 집어넣어놓은 후 마지막에 한번에 확산시켰다.

 

확산은 그렇게 어렵지 않게 짰는데, 시프팅 하는게 나만 그런지는 몰라도 너무 머리가 아프다.

 

+1,-1 경계값때문에 너무 헷갈려서 시간을 많이 버렸다.