[파이썬] SWEA 5653 : 줄기세포배양(test)

[파이썬] SWEA 5653 : 줄기세포배양(test)

• SWEA 5653 : 줄기세포배양

---

풀이

방향성 생각

• 힙을 사용해서 매 시각마다 이벤트를 처리하지 않고, 필요한 시점에만 이벤트를 계산하기.
• 시간에 대해서는 최소힙을 사용한다.
• 생명력 수치에 대해서는 최대힙을 사용한다.
• 배열의 크기는 정해지지 않았으니, set을 사용해서 방문처리를 한다.

 

전체코드

import heapq as hq

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

TC = int(input())
for tc in range(1,TC+1):

    H,W,T = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(H)]

    V = set()
    heap = []
    live = []

    # 시작점을 힙에 추가, 방문 추가, 생명 주기 관리해주기기
    for y in range(H):
        for x in range(W):
            if arr[y][x]:
                V.add((x,y))
                life = arr[y][x]
                hq.heappush(heap,(0,-life,1,x,y))
                live.append((0, life))

    while heap:

        # 현재 시각이 t보다 커지면 탈출하기
        if heap[0][0] >= T:
            break

        # 시간, 생명력 수치, 상태, x좌표, y좌표
        t,val,state,x,y = hq.heappop(heap)

        # 비활성 상태인 경우, val 시간 후후
        if state == 1:
            hq.heappush(heap,(t+abs(val),val,2,x,y))

        # 활성 상태인 경우, 주변에 퍼뜨린다. t+1시점에 추가 (최대힙이라서 먼저 뽑힌 세포가 먼저 퍼뜨린다다)
        elif state == 2:

            for dx,dy in dires:
                nx,ny = x+dx,y+dy
                if (nx,ny) not in V:
                    V.add((nx,ny))
                    hq.heappush(heap,(t+1,val,1,nx,ny))
                    live.append((t+1, -val))

    # 시간 조건에 맞는애만 뽑기기
    answer = 0
    for t0,life in live:
        if T < t0 + 2*life:
            answer += 1

    print(f"#{tc} {answer}")

코멘트

• 시뮬레이션보단 힙을 쓰는게 좀 더 의도에 맞는 풀이가 아니었나..