SW Expert Academy 2382. [모의 SW 역량테스트] 미생물 격리

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl

SW Expert Academy

이 문제의 핵심은 각 시간마다 미생물들이 이동하는 것을 잘 구현하는가와 미생물들이 겹쳤을 때 1개로 합쳐주는 것을 잘 구현하는가이다. 매번 셀 전체를 복사하는 것 대신에 딕셔너리를 통해서 필요한 좌표들의 값만 처리하여 효율성을 높였다. 파이썬은 배열을 마구 사용하면 시간 초과되기 십상이기 때문이다. 아래는 내가 해결한 코드이다.

t = int(input())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for test in range(1, t + 1):
    dic = {}
    n, m, k = map(int, input().split())
    micros = []
    answer = 0
    for _ in range(k):
        x, y, number, dire = map(int, input().split())
        dire -= 1
        micros.append([x, y, number, dire])

    t = 0
    while t < m:
        t += 1
        for i in micros:
            i[0] += dx[i[3]]
            i[1] += dy[i[3]]
            if i[0] == 0 or i[0] == n - 1 or i[1] == 0 or i[1] == n - 1:
                i[2] = i[2] // 2
                if i[3] == 0:
                    i[3] = 1
                elif i[3] == 1:
                    i[3] = 0
                elif i[3] == 2:
                    i[3] = 3
                else:
                    i[3] = 2
            if dic.get((i[0], i[1])) is None:
                dic[(i[0], i[1])] = [i]
            else:
                dic[(i[0], i[1])].append(i)
        micros = []
        for i in dic.keys():
            if len(dic[i]) > 1:
                nd = -1
                mav = 0
                number = 0
                for u in dic[i]:
                    if u[2] > mav:
                        mav = u[2]
                        nd = u[3]
                    number += u[2]
                micros.append([i[0], i[1], number, nd])
            else:
                micros.append([i[0], i[1], dic[i][0][2], dic[i][0][3]])
        dic = {}
    for i in micros:
        answer += i[2]
    print('#{} {}'.format(test, answer))