1 minute read

문제

접근 방법

50x50x1000 –> 시간 복잡도는 고려하지 않고 그대로 구현만 하면 된다고 생각했다.

  1. 공기청정기와 미세먼지의 위치를 입력받고 위쪽 공기청정기의 공기 흐름과 아래쪽 공기청정기 공기 흐름을 함수로 구현했다. –> 이런 시뮬레이션 코드는 처음이라 힘들었다.
  2. 확산 함수를 구현
  3. 1초가 지날 때마다 순서대로 실행시킨다. 이때 확산을 하면서 새로 생긴 미세먼지 위치는 추가하고 없어진 위치는 없애야 한다.

확산을 구현할 때가 어려웠다. 각 미세먼지를 동시에 확산시키는 방법을 생각해내는게 어려웠다. 처음에는 미세먼지 위치만 저장해서 구현하려고 했는데 그렇게 하면 한 곳이 확산될 때 다른 곳이 영향을 받을 수 있다. 따라서 위치뿐만 아니라 값까지 따로 빼놓고 확산시키면 동시에 확산을 시킬 수 있다.

정답 코드


import sys
input = sys.stdin.readline

r,c,t = map(int, input().split())
maps = []
for _ in range(r):
    maps.append(list(map(int, input().split())))

"""
1000*50*50 --> 2500000 그냥 하라는대로 하면 될 듯
"""

#공기청정기, 먼지 위치
air = []
dust = []
for i in range(r):
    for j in range(c):
        if maps[i][j] == -1:
            air.append((i,j))
        elif maps[i][j] > 0:
            dust.append((i,j,maps[i][j]))

#1초마다 공기 방향대로 움직이게 하는 함수
up_air = air[0][0]
down_air = air[1][0]

def up_air_move():
    for h in range(up_air-1, 0, -1):
        maps[h][0] = maps[h-1][0]
    for w in range(c-1):
        maps[0][w] = maps[0][w+1]
    for h in range(up_air):
        maps[h][c-1] = maps[h+1][c-1]
    for w in range(c-1, 1, -1):
        maps[up_air][w] = maps[up_air][w-1]
    maps[up_air][1] = 0

def down_air_move():
    for h in range(down_air+1, r-1):
        maps[h][0] = maps[h+1][0]
    for i in range(c-1):
        maps[r-1][i] = maps[r-1][i+1]
    for h in range(r-1, down_air, -1):
        maps[h][c-1] = maps[h-1][c-1]
    for i in range(c-1, 0, -1):
        maps[down_air][i] = maps[down_air][i-1]
    maps[down_air][1] = 0

def get_ans():
    ans = 0
    for h in range(r):
        for w in range(c):
            if maps[h][w] > 0:
                ans+=maps[h][w]
    print(ans)

moves = [(-1,0), (0,1), (1,0), (0,-1)]

#확산 함수
def spread_dust():
    while dust:
        h,w,v = dust.pop()
        cnt = 0
        for dh,dw in moves:
            new_h = h+dh
            new_w = w+dw
            if 0<=new_h<r and 0<=new_w<c and maps[new_h][new_w] != -1:
                maps[new_h][new_w] += v//5
                cnt+=1
        maps[h][w] -= (v//5) * cnt
                

for _ in range(t):
    dust = []
    spread_dust()
    up_air_move()
    down_air_move()
    for h in range(r):
        for w in range(c):
            if maps[h][w] > 0:
                dust.append((h,w,maps[h][w]))
get_ans()

You May Also Enjoy