SWEA 5653. [모의 SW 역량테스트] 줄기세포배양

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo&categoryId=AWXRJ8EKe48DFAUo&categoryType=CODE&problemTitle=%EC%A4%84%EA%B8%B0%EC%84%B8%ED%8F%AC&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

---

솔루션

from collections import deque

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

def simulate_growth(N, M, K, initial_grid):
    size = 350
    offset = 150 
    grid = [[0] * size for _ in range(size)]
    cells = deque()

    # 초기화
    for i in range(N):
        for j in range(M):
            if initial_grid[i][j] > 0:
                x, y = i + offset, j + offset
                grid[x][y] = initial_grid[i][j]
                cells.append((x, y, initial_grid[i][j], 'inactive', initial_grid[i][j]))

    for _ in range(K):
        next_cells = deque()
        reproduce_candidates = {}

        while cells:
            x, y, life, state, remaining = cells.popleft()

            if state == 'inactive': 
                if remaining > 1:
                    next_cells.append((x, y, life, 'inactive', remaining - 1))
                else:
                    next_cells.append((x, y, life, 'active', life))
            elif state == 'active':
                if remaining > 1:
                    next_cells.append((x, y, life, 'active', remaining - 1))
                else:
                    grid[x][y] = -1 

                # 번식
                if remaining == life:  
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if grid[nx][ny] == 0:  
                            if (nx, ny) not in reproduce_candidates:
                                reproduce_candidates[(nx, ny)] = life
                            else:
                                reproduce_candidates[(nx, ny)] = max(reproduce_candidates[(nx, ny)], life)

        for (nx, ny), max_life in reproduce_candidates.items():
            if grid[nx][ny] == 0: 
                grid[nx][ny] = max_life
                next_cells.append((nx, ny, max_life, 'inactive', max_life))

        cells = next_cells

    alive_count = 0
    for x in range(size):
        for y in range(size):
            if grid[x][y] > 0:
                alive_count += 1

    return alive_count

T = int(input())  
for t in range(1, T + 1):
    N, M, K = map(int, input().split()) 
    initial_grid = [list(map(int, input().split())) for _ in range(N)]
    result = simulate_growth(N, M, K, initial_grid)
    print(f"#{t} {result}")

---

깨달은 점

어렵다..

 

줄기세포배양함수 코드설명

size = 350  # 충분히 큰 그리드 크기
offset = 150  # 초기 그리드를 중앙에 배치하기 위한 오프셋
grid = [[0] * size for _ in range(size)]  # 확장된 그리드 생성
cells = deque()  # 살아있는 줄기 세포 상태 저장

초기 그리드를 확장하여 무한 배양 용기를 지원

 

for i in range(N):
    for j in range(M):
        if initial_grid[i][j] > 0:  # 줄기 세포가 있는 경우
            x, y = i + offset, j + offset  # 확장된 그리드에서의 좌표
            grid[x][y] = initial_grid[i][j]
            cells.append((x, y, initial_grid[i][j], 'inactive', initial_grid[i][j]))

초기화

• 초기 그리드에서 줄기 세포가 있는 좌표만 cells 큐에 추가, 상태는 비활성 상태(inactive)로 시작

for _ in range(K):
    next_cells = deque()  # 다음 시간의 줄기 세포 상태
    reproduce_candidates = {}  # 번식 후보 위치와 생명력 저장 딕셔너리

K시간 동안 시뮬레이션

 

   while cells:
        x, y, life, state, remaining = cells.popleft()

        if state == 'inactive':  # 비활성 상태
            if remaining > 1:
                next_cells.append((x, y, life, 'inactive', remaining - 1))
            else:
                next_cells.append((x, y, life, 'active', life))

세포 상태 처리

비활성 상태(inactive):

• remaining > 1: 비활성 상태를 유지하며 남은 시간을 1 줄임
• remaining == 1: 다음 시간에 활성 상태(active)로 전환

        elif state == 'active':  # 활성 상태
            if remaining > 1:
                next_cells.append((x, y, life, 'active', remaining - 1))
            else:
                grid[x][y] = -1  # 죽은 상태로 표시

            if remaining == life:  # 활성화된 첫 시간
                for dx, dy in directions:  # 상하좌우로 번식
                    nx, ny = x + dx, y + dy
                    if grid[nx][ny] == 0:  # 빈 공간만 번식 가능
                        if (nx, ny) not in reproduce_candidates:
                            reproduce_candidates[(nx, ny)] = life
                        else:
                            reproduce_candidates[(nx, ny)] = max(reproduce_candidates[(nx, ny)], life)

활성 상태(active):

• remaining > 1: 활성 상태를 유지하며 남은 시간을 1 줄입니다.
• remaining == 1: 활성 상태가 끝나고 죽은 상태로 전환.
• 번식 처리:
  • 활성화된 첫 시간에 상하좌우로 번식.
  • 번식 위치에 여러 세포가 번식하려 할 경우 생명력이 가장 높은 세포를 선택.

    for (nx, ny), max_life in reproduce_candidates.items():
        if grid[nx][ny] == 0:  # 번식 가능한 경우
            grid[nx][ny] = max_life
            next_cells.append((nx, ny, max_life, 'inactive', max_life))

번식처리

 

• 번식 후보 중 생명력이 가장 높은 세포가 번식.
• 번식된 세포는 비활성 상태로 추가.

    cells = next_cells  # 다음 시간의 세포 상태로 갱신

alive_count = 0
for x in range(size):
    for y in range(size):
        if grid[x][y] > 0:  # 비활성 상태 또는 활성 상태
            alive_count += 1

 

결과 계산 (살아있는 세포(비활성 또는 활성 상태)의 개수)