미세먼지 안녕! ( 17144번 )

17144번: 미세먼지 안녕!

 

나의 풀이

import sys

def _cr_result(R, C, map_list):
    answer = 0
    for i in range(R):
        for j in range(C):
            if (map_list[i][j] != 0) and (map_list[i][j] != -1):
                answer += map_list[i][j]
    return answer

def _on_air(map_list, R, C, a_idx, b_idx):
    for idx in range(a_idx-1, 0 , -1):
        map_list[idx][0] = map_list[idx-1][0]
    for idx in range(C-1):
        map_list[0][idx] = map_list[0][idx + 1]
    for idx in range(0, a_idx):
        map_list[idx][C-1] = map_list[idx+1][C-1]
    for idx in range(C-1, 0, -1):
        if (idx == 1):
            map_list[a_idx][idx] = 0
        else:
            map_list[a_idx][idx] = map_list[a_idx][idx - 1]

    for idx in range(b_idx + 1, R - 1):
        map_list[idx][0] = map_list[idx+1][0]
    for idx in range(C-1):
        map_list[R-1][idx] = map_list[R-1][idx+1]
    for idx in range(R-1, b_idx, -1):
        map_list[idx][C-1] = map_list[idx-1][C-1]
    for idx in range(C-1, 0, -1):
        if (idx == 1):
            map_list[b_idx][idx] = 0
        else:
            map_list[b_idx][idx] = map_list[b_idx][idx-1]
    return map_list

def _gogo(map_list, R, C, first_a, second_a):
    new_map_list = [[0] * C for _ in range(R)]
    new_map_list[first_a[0]][first_a[1]], new_map_list[second_a[0]][second_a[1]] = -1, -1

    for i in range(R):
        for j in range(C):
            if (map_list[i][j] != 0) and (map_list[i][j] != -1):
                gogo_ct = 0
                for m_i, m_j in ((-1,0),(1,0),(0,-1),(0,1)):
                    next_i, next_j = (i + m_i), (j + m_j)
                    if (0 <= next_i < R) and (0 <= next_j < C) and (map_list[next_i][next_j] != -1):
                        gogo_ct += 1
                        new_map_list[next_i][next_j] += int(map_list[i][j] / 5)
                new_map_list[i][j] += (map_list[i][j] - (gogo_ct * int(map_list[i][j] / 5)))
    return new_map_list

def _main(R, C, T, map_list, first_a, second_a):
    for _ in range(T):
        map_list = _gogo(map_list, R, C, first_a, second_a)
        _on_air(map_list, R, C, first_a[0], second_a[0])
    answer = _cr_result(R, C, map_list)
    return answer

R, C, T = map(int, sys.stdin.readline().rstrip().split())
map_list, first_a, second_a = [], (), ()
for idx in range(R):
    append_list = list(map(int, sys.stdin.readline().rstrip().split()))
    if (-1 in append_list):
        if first_a:
            second_a = (idx, append_list.index(-1))
        else:
            first_a = (idx, append_list.index(-1))
    map_list.append(append_list)
    
print(_main(R, C, T, map_list, first_a, second_a))

 

시간 복잡도

for _ in range(T) : 주어진 초 만큼 순회 ( 선형 시간 )
    map_list = _gogo(map_list, R, C, first_a, second_a) : 먼지 확산 함수 ( 이차형 시간 )
    _on_air(map_list, R, C, first_a[0], second_a[0]) : 에어컨 함수 ( 선형 시간 )
answer = _cr_result(R, C, map_list) : 최종 계산 함수 ( 이차형 시간 )

해당 알고리즘 시간 복잡도 : 삼차형 시간 복잡도 ( O(n ** 3) )