[백준][Python] 17144 미세먼지 안녕

구현중 가장 귀찮은 구현이 배열 회전인것같다..

확산, 회전순으로 과정압축없이 진행

위는 내코드 아래는 1등코드 1등코드는 내 코드보다 10배 빠르다.

차이점은 dusts를 배열로 관리했다는 것. 불필요한 과정이었던것같다.

 

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


def rotate_dust():
    up_cycle = deque()
    down_cycle = deque()
    up_cycle_down, down_cycle_up = air_clear[0][0], air_clear[1][0]

    # 0, 공기청정기 x 작은 좌표, 좌, 우 -> rotate(-1)
    for i in range(C):
        up_cycle.append(matrix[0][i])
    for i in range(1, up_cycle_down):
        up_cycle.append(matrix[i][C-1])
    for i in range(C-1, -1, -1):
        up_cycle.append(matrix[up_cycle_down][i])
    for i in range(up_cycle_down-1, 0, -1):
        up_cycle.append(matrix[i][0])
    up_cycle.rotate(-1)
    for i in range(C):
        matrix[0][i] = up_cycle.popleft()
    for i in range(1, up_cycle_down):
        matrix[i][C-1] = up_cycle.popleft()
    for i in range(C-1, -1, -1):
        matrix[up_cycle_down][i] = up_cycle.popleft()
    for i in range(up_cycle_down-1, 0, -1):
        matrix[i][0] = up_cycle.popleft()
    matrix[air_clear[0][0]][air_clear[0][1]] = 0

    # R, 공기청정기 x 큰 좌표, 좌, 우 -> rotate(1)
    for i in range(C):
        down_cycle.append(matrix[down_cycle_up][i])
    for i in range(down_cycle_up + 1, R):
        down_cycle.append(matrix[i][C-1])
    for i in range(C-2, -1, -1):
        down_cycle.append(matrix[R-1][i])
    for i in range(R - 2, down_cycle_up, -1):
        down_cycle.append(matrix[i][0])
    down_cycle.rotate(1)
    for i in range(C):
        matrix[down_cycle_up][i] = down_cycle.popleft()
    for i in range(down_cycle_up + 1, R):
        matrix[i][C-1] = down_cycle.popleft()
    for i in range(C-2, -1, -1):
        matrix[R-1][i] = down_cycle.popleft()
    for i in range(R - 2, down_cycle_up, -1):
        matrix[i][0] = down_cycle.popleft()
    matrix[air_clear[1][0]][air_clear[1][1]] = 0



def spread_dust(dusts):
    new_dusts = []

    for dust in dusts:
        x, y = dust
        init_dust = matrix[x][y]
        cnt = 0
        for dx, dy in delta:
            nx, ny = x + dx, y + dy
            if 0 <= nx < R and 0 <= ny < C and not (nx, ny) in air_clear:
                new_dusts.append((nx, ny, init_dust//5))
                cnt += 1
        new_dusts.append((x, y, init_dust - cnt * (init_dust//5)))
        matrix[x][y] = 0

    for dust in new_dusts:
        x, y, a = dust
        matrix[x][y] += a


delta = ((0, -1), (1, 0), (-1, 0), (0, 1))

R, C, T = map(int, input().split())
matrix = []
air_clear = []
dusts = []
for i in range(R):
    row = list(map(int, input().split()))
    for j in range(C):
        if row[j] == -1:
            air_clear.append((i,j))
            row[j] = 0
        elif row[j]:
            dusts.append((i,j))
    matrix.append(row)

for __ in range(T):
    # 1. 미세먼지 확산.
    spread_dust(dusts)
    # 2. 공기청정기 작동. 원 2개 순환.
    rotate_dust()

    answer = 0
    dusts = []
    for i in range(R):
        for j in range(C):
            if matrix[i][j]:
                dusts.append((i,j))
                answer += matrix[i][j]
print(answer)

 

 

1등코드

2차원이 아닌 1차원에서 진행했다. deque를 쓴것이랑 dusts를 따로 관리한게 불필요했던 것 같다. 어차피 먼지가 거의 전역에 퍼지기때문에 그냥 2중 for문으로 순회하면서 퍼지게 했으면 더 빨랐을지도?

R, C, T = [int(_) for _ in input().split(' ')]
M = []
S = [0]*(R*C)
ac = -1

for i in range(R):
    l = [int(_) for _ in input().split(' ')]
    if l[0] == -1 and ac == -1:
        ac = i
    M += l

def move(fi, fj, ti, tj):
    if (fi, fj) == (ti, tj):
        return

    if fi == ti:
        if fj < tj:
            for j in range(tj, fj, -1):
                M[fi*C+j] = M[fi*C+j-1]
        else:
            for j in range(tj, fj):
                M[fi*C+j] = M[fi*C+j+1]
    elif fi < ti:
        for i in range(ti, fi, -1):
            M[i*C+fj] = M[i*C-C+fj]
    else:
        for i in range(ti, fi):
            M[i*C+fj] = M[i*C+C+fj]
    M[fi*C+fj] = 0

def move_rect(start, edge):
    move(edge, 0, start, 0)
    M[start*C] = 0
    move(edge, C-1, edge, 0)
    move(start, C-1, edge, C-1)
    move(start, 0, start, C-1)

for _ in range(T):
    for v in range(R*C):
        if M[v] < 0: continue
        msp = M[v] // 5
        
        i = v//C
        j = v%C

        if i > 0 and M[v-C]>=0:
            M[v] -= msp
            S[v-C] += msp
        if i < R-1 and M[v+C]>=0:
            M[v] -= msp
            S[v+C] += msp
        if j > 0 and M[v-1]>=0:
            M[v] -= msp
            S[v-1] += msp
        if j < C-1 and M[v+1]>=0:
            M[v] -= msp
            S[v+1] += msp

    for v in range(R*C):
        M[v] += S[v]
        S[v] = 0
        
    if ac == -1:
        continue

    M[ac*C] = -1
    M[ac*C+C] = -1
    
    move_rect(ac, 0)
    move_rect(ac+1, R-1)
    
    M[ac*C] = -1
    M[ac*C+C] = -1

print(2+sum(M))