[SWEA][D4][#02382] 미생물 격리

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

문제 생략

My Sol

from collections import deque

def checkSum(Q):
    Q2 = list(Q)
    Q2.sort(key=lambda x: (x[0], x[1]))
    Q2.append((0, 0, 0, 1))
    Q3 = deque()
    tmp = []
    c1, c2 = -1, -1
    for g in Q2:
        if not tmp:
            tmp.append(g)

        elif g[0]==c1 and g[1]==c2:
            tmp.append(g)

        else:
            # 같은 좌표 도착 군집 tmp에 2개 이상
            if len(tmp) > 1:
                tmp.sort(reverse=True, key=lambda x:x[2])
                kg = tmp[0]
                fi, fj = kg[0], kg[1]
                fd = kg[3]
                fsize = 0
                for tg in tmp:
                    fsize += tg[2]
                Q3.append((fi, fj, fsize, fd))
            else:
                Q3.append(tmp[0])
            tmp = [g]
        c1, c2 = g[0], g[1]
    return Q3


ref = {1:2, 2:1, 3:4, 4:3}
dictV = {1: (-1,0), 2: (1,0), 3: (0,-1), 4: (0,1)}

T = int(input())
for tc in range(1, T+1):
    N, M, K = map(int, input().split())
    Q = deque()
    for _ in range(K):
        Q.append(tuple(map(int, input().split())))

    t = 0
    while t < M:
        LQ = len(Q)
        for _ in range(LQ):
            ni, nj, size, nd = Q.popleft()
            di, dj = dictV[nd]
            si, sj = ni+di, nj+dj

            # 약품 지역 도착 안 하면
            if 0<si<N-1 and 0<sj<N-1:
                Q.append((si, sj, size, nd))
            # 약품 지역 도착하면
            else:
                # size가 2 이상일 때만 Q에 추가
                if size//2:
                    Q.append((si, sj, size//2, ref[nd]))

        Q = checkSum(Q)
        t += 1

    ret = 0
    for g in Q:
        ret += g[2]

    print(f'#{tc} {ret}')

while 문 내에 for문을 배치해서 Q 내의 군집의 개수만큼 for문을 돌려준다. for문 내에서는 각 군집을 뽑아 약품 지역에 도착하는지 안 하는지에 대한 정보를 확인하는데, 만약에 약품지역에 도착한다면 방향을 반대로 바꾸고 size를 //2 해주어야 한다. 이 과정에서 ref 딕셔너리를 두어, 현재 진행방향의 반대방향을 두는데 편의를 두었다. 만약 size//2가 0이라면 Q에 추가할 필요가 없으므로 size//2가 1 이상인 경우에만 Queue에 추가한다.

좌표에 표시하지 않고 Q에 추가하는 이유는 1시간이 지난 후 어떤 특정 좌표에 군집이 중첩된다면 이중에서 우세 군집을 선정해서 합쳐주어야 하기 때문이다. 이를 위해 같은 좌표에 도착하는 그룹들을 tmp에 모아두고, 다른 좌표의 군집이 시작된다면 tmp를 처리하여 Q3에 추가한 뒤, tmp에 이번 군집을 추가해 넘겨준다.

마지막에 0,0 좌표의 가상 군집을 추가한 이유는 tmp에 남아있는 군집들을 처리하여 Q3에 추가하기 위해서이다. 0,0 좌표의 가상 군집이 tmp에 어떻게 남아있든 상관할 일이 아니다. 이렇게 Q3를 완성하고 반환해주면, 이를 함수 외부에서 받고, t를 1 추가해준다. 이 일련이 과정이 1시간동안 진행되었음을 의미한다.

이 반복이 t번, 즉 t시간동안 진행되면, while문이 종료되고, 종료 이후 남은 Q의 군집들의 size의 합을 계산해 출력해주면 되겠다.

결과

PASS