SWEA 5653 줄기세포배양

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo&categoryId=AWXRJ8EKe48DFAUo&categoryType=CODE&problemTitle=%EB%AA%A8%EC%9D%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

요약: K시간 후 살아있는 줄기 세포(비활성 상태 + 활성 상태)의 총 개수를 구하는 프로그램을 작성

이 문제에서 가장 어려운점 하나는 배양할 수 있는 공간이 무한정이라는 것이다.
따라서 2차원 배열이 무한정 늘어날 수 있기 때문에 색다른 접근 방식이 필요할 것이라고 생각했다.

그래서 defaltdict의 key를 활용해 세포가 있는 cell의 좌표를 관리해보았다.
다음과 같이

• dictionary의 key -> cell의 좌표
• dictionary의 value -> [시작 시간, 수명]
  • 따라서 초기 세포들은 [0, 입력값]으로 설정

for i in range(N):
	for j in range(M):
    	# [시작 시간, 수명]
        if grid[i][j] != 0: can_active[(i, j)] = [0, grid[i][j]]

이 기본 셋팅을 바탕으로 세포들을 관리한다.

• can_active: 비활성화 상태의 세포들
• generate: 막 활성화 되어, 증식해야하는 세포들
• activate: 증식은 끝났지만, 수명이남은 세포들
• dead_cell: 수명이다한 세포들

dead_cell은 유지되는 정보이기 때문에 testcase가 변할때만 초기화 해주면된다.
generate의 경우 막활성화된 다음 time에만 증식을 하기 때문에 매시간 초기화 해주어야한다.
activate can_active의 경우, 매시간 new를 붙인 변수를 활용해 정보를 업데이트 해주어야 한다.

매시간 일어나는 일은 다음과 같다.

1. 이번 시간에 증식하는 세포들 증식 및 activate에 추가
  - 세포가 있는 곳에는 증식 불가능
  - 증식한 세포는 활성화 되어있기 때문에 activate에 추가
2. generate 초기화 
  - 증식은 최초 1시간만 하기 때문에 초기화해주어야 한다.
3. 이번 시간에 활성화 되는 세포, generate에 추가, 비활성화 상태 유지 new_can_activate에 추가
  - 생성시간(put_time) + 수명(life) 이 현재 time과 같으면 genrate에 추가
  - 아니면, 비활성화 상태 유지
4. activate에서 수명을 다한 세포들 new_active에 추가
  - 현재 time이 최종 수명(put_time + (life*2)) 보다 작으면 new_activate에 추가
  - 크면 죽은 세포임으로 dead_cell에 추가
5. activate, can_activate 값 업데이트

상세코드는 다음과 같다.

전체 코드

"""
Author:
    Name: KyungHyun Lim
    Email: lkh1075@gmail.com
"""
from collections import defaultdict

def simulation(can_active, activate, K):
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    generate = defaultdict(list)
    dead_cell = defaultdict(list)
    for time in range(K + 1):
        new_can_active = defaultdict(list)
        # 이번 시간에 생성되는 세포 추가
        for cord, item in generate.items():
            put_time, life = item
            for d in range(4):
                nx, ny = cord[0] + dx[d], cord[1] + dy[d]
                if (nx, ny) not in can_active and (nx, ny) not in activate and (nx, ny) not in generate and (nx, ny) not in dead_cell: # 세포가 있는 자리가 아니면
                    if (nx, ny) in new_can_active:
                        life = max(life, new_can_active[(nx, ny)][1]) # 주변에 세포 생성
                        new_can_active[(nx, ny)] = [time, life]
                    else:
                        new_can_active[(nx, ny)] = [time, life]
        
            activate[cord] = item
        
        # 이번 시간에 활성화 되는 세포, 다음 타임에 생성하도록 추가
        generate = defaultdict(list)
        for cord, item in can_active.items():
            put_time, life = item
            if put_time + life == time: # 활성화됨, + 1 time에 생성
                generate[(cord)] = item
            else: # 활성화 되지 않으면 유지
                new_can_active[(cord)] = item
        
        new_active = defaultdict(list)
        # 죽음 처리
        for cord, item in activate.items():
            put_time, life = item
            if time < put_time + (life*2):
                new_active[cord] = item
            else:
                dead_cell[cord] = item
                
        activate = new_active
        can_active = new_can_active
        
        # print(f'T: {time}')
        # print(f'activated cell: {generate}')
        # print(f'deactivated cell: {can_active}')
        # print(f'alive cell: {activate}')
        # print(f'dead_cell: {dead_cell}')
        
            
    return len(activate) + len(can_active) + len(generate)

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # 세로크기, 가로크기, 시뮬레이션 시간
    N, M, K = list(map(int, input().split()))
    grid = [list(map(int, input().split())) for i in range(N)]
    
    activate = defaultdict(list)
    can_active = defaultdict(list)
    
    for i in range(N):
        for j in range(M):
            # [시작 시간, 수명]
            if grid[i][j] != 0: can_active[(i, j)] = [0, grid[i][j]]
    
    print(f'#{test_case} {simulation(can_active, activate, K)}')