SW Expert Academy의 모의 SW 역량 테스트 문제들을 풀고 있다.
문제
줄기세포 배양 시뮬레이션 프로그램을 만들려고 한다.
줄기세포들을 배양 용기에 도포한 후 일정 시간 동안 배양을 시킨 후 줄기 세포의 개수가 몇 개가 되는지 계산하는 시뮬레이션 프로그램을 만들어야 한다.
하나의 줄기 세포는 가로, 세로 크기가 1인 정사각형 형태로 존재하며 배양 용기는 격자 그리드로 구성되어 있으며 하나의 그리드 셀은 줄기 세포의 크기와 동일한 가로, 세로 크기가 1인 정사각형이다.
각 줄기 세포는 생명력이라는 수치를 가지고 있다.
초기 상태에서 줄기 세포들은 비활성 상태이며 생명력 수치가 X인 줄기 세포의 경우 X시간 동안 비활성 상태이고 X시간이 지나는 순간 활성 상태가 된다.
줄기 세포가 활성 상태가 되면 X시간 동안 살아있을 수 있으며 X시간이 지나면 세포는 죽게 된다.
세포가 죽더라도 소멸되는 것은 아니고 죽은 상태로 해당 그리드 셀을 차지하게 된다.
활성화된 줄기 세포는 첫 1시간 동안 상, 하, 좌, 우 네 방향으로 동시에 번식을 한다.
번식된 줄기 세포는 비활성 상태이다.
하나의 그리드 셀에는 하나의 줄기 세포만 존재할 수 있기 때문에 번식하는 방향에 이미 줄기 세포가 존재하는 경우 해당 방향으로 추가적으로 번식하지 않는다.
두 개 이상의 줄기 세포가 하나의 그리드 셀에 동시 번식하려고 하는 경우 생명력 수치가 높은 줄기 세포가 해당 그리드 셀을 혼자서 차지하게 된다.
줄기 세포의 크기에 비해 배양 용기의 크기가 매우 크기 때문에 시뮬레이션에서 배양 용기의 크기는 무한하다고 가정한다.
아래 [그림1]과 [그림2]는 줄기 세포가 번식하는 예를 나타낸다.
줄기 세포의 초기 상태 정보와 배양 시간 K시간이 주어질 때, K시간 후 살아있는 줄기 세포(비활성 상태 + 활성 상태)의 총 개수를 구하는 프로그램을 작성하라.
제약 사항
초기 상태에서 줄기 세포가 분포된 영역의 넓이는 세로 크기 N, 가로 크기 M이며 N, M은 각각 1 이상 50 이하의 정수이다. (1≤N≤50, 1≤M≤50)
배양 시간은 K시간으로 주어지며 K는 1 이상 300 이하의 정수이다. (1≤K≤300)
배양 용기의 크기는 무한하다. 따라서 줄기 세포가 배양 용기 가장자리에 닿아서 번식할 수 없는 경우는 없다.
줄기 세포의 생명력 X는 1 이상 10 이하의 정수이다. (1≤X≤10)
입력
입력의 가장 첫 줄에는 총 테스트 케이스의 개수 T가 주어진다.
그 다음 줄부터는 각 테스트 케이스가 주어지며
각 테스트 케이스의 첫째 줄에는 초기 상태에서줄기 세포가 분포된 세로 크기 N, 가로 크기 M, 배양 시간 K가 순서대로 주어진다.
다음 N 줄에는 각 줄마다 M개의 그리드 상태 정보가 주어진다.
1~10까지의 숫자는 해당 그리드 셀에 위치한 줄기 세포의 생명력을 의미하며,
0인 경우 줄기 세포가 존재하지 않는 그리드이다.
문제 풀이
재귀를 사용한 구현으로 풀었다.
댓글에서 배양 용기의 최대 사이즈는 max(N, M) + Kx2라는 말을 보고 최대 사이즈를 똑같이 설정했다. (N또는 M에서 양 옆으로 K만큼 빠져나간다고 하면 최대는 max(N, M) + Kx2가 될 수 밖에 없다.)
그런데 문제를 아직 시간초과로 완전히 풀지 못했다 (5개의 테스트 케이스는 통과한다.)
시간 초과를 해결하기 위해 용기 사이즈를 이리저리 조절해보다가 용기 사이즈를 380으로 설정해도 된다는 사실을 알게 되었다.
각 시간당 일어날 일들을 문제에서 잘 파악한 뒤에 그대로 구현하면 된다.
조금 더 자세하게 설명하자면 배양 용기 사이즈만큼의 2차원 행렬 2개와 각 좌표당 에너지(생명력)을 저장하는 dictionary를 하나 사용한다.
첫번째 2차원 행렬은 시간(생명력)을 저장하고 두번째 행렬은 상태(비활성화, 활성화, 죽음)를 저장한다
행렬의 모든 좌표를 돌면서 각 좌표에 세포가 있다면 비활성 상태인지 활성 상태인지 파악하고 비활성 상태인데 시간이 0이라면 활성상태로 바꾸는 등 각 상황에 맞는 작업들을 수행한다.
시간초과가 발생하는 원인으로 생각되는건 아마 세포가 번식할 때 번식할 세포의 좌표를 리스트에 모아놨다가 시간을 +1 하기 전에 한번에 번식하는데 여기서 발생하는 것이 아닐까 싶다..
혹시 지나가던 누구든 무엇이 문제인지 알 것 같다면 알려주길 바란다...
‼️ 각 시간별로 일어나는 일들을 꼼꼼하게 잘 생각해서 구현 해야한다.
내가 실수 했던 부분을 몇가지 기록해 두자면 세포는 활성 상태가 된 1시간 이후에 번식한다.
번식하고 나서도 바로 죽는 것이 아니라 세포의 시간이 점점 줄어들다가 0이 되면 죽는다.
번식할 때 동시에 번식하는 세포 중 생명력이 더 큰 세포와 번식할 자리(?)가 겹치면 생명력이 더 큰 세포의 생명력으로 번식해야한다.
이 우선순위 처리 하는 것도 깜빡해서 헤맸다.
💡 상태를 표현하는 숫자들을 INACTIVE, ACTIVE, DIE와 같은 상수로 선언하여 코드가 더 예뻐졌다
코드
import sys
sys.stdin = open("sample_input.txt", "r")
DIRECTION_X = [-1, 1, 0, 0]
DIRECTION_Y = [0, 0, -1, 1]
INACTIVE = 2
ACTIVE = 1
DIE = 0
NOT_EXIST = -1
MAX_RANGE = 380
def breeding(arr):
visited = list()
# 우선 순위
for x, y in arr:
for idx in range(4):
new_x = x + DIRECTION_X[idx]
new_y = y + DIRECTION_Y[idx]
if curr_status_map[new_x][new_y] == NOT_EXIST:
curr_status_map[new_x][new_y] = INACTIVE
curr_time_map[new_x][new_y] = energy_dict[(x, y)] - 1
energy_dict[(new_x, new_y)] = energy_dict[(x, y)]
visited.append([new_x, new_y])
elif [new_x, new_y] in visited:
if energy_dict[(new_x, new_y)] < energy_dict[(x, y)]:
curr_time_map[new_x][new_y] = energy_dict[(x, y)] - 1
energy_dict[(new_x, new_y)] = energy_dict[(x, y)]
def multiply_cells(time):
if time == K+1:
return
breeding_list = list()
for n in range(MAX_RANGE):
for m in range(MAX_RANGE):
if curr_time_map[i][j] == NOT_EXIST:
# 비활성 상태
if curr_status_map[n][m] == INACTIVE:
if curr_time_map[n][m] == 0:
curr_status_map[n][m] = ACTIVE
curr_time_map[n][m] = energy_dict[(n, m)]
else:
curr_time_map[n][m] -= 1
# 활성 상태
elif curr_status_map[n][m] == ACTIVE:
if curr_time_map[n][m] == energy_dict[(n, m)]:
breeding_list.append((n, m))
curr_time_map[n][m] -= 1
if curr_time_map[n][m] == 0:
curr_status_map[n][m] = DIE
breeding(breeding_list)
multiply_cells(time+1)
T = int(input())
for test_case in range(T):
count = 0
grid_map = list()
N, M, K = map(int, input().split()) # 세로 크기 N, 가로 크기 M, 배양 시간 K
# max_range = max(N, M) + K * 2
curr_time_map = [[NOT_EXIST for _ in range(MAX_RANGE)] for _ in range(MAX_RANGE)]
curr_status_map = [[NOT_EXIST for _ in range(MAX_RANGE)] for _ in range(MAX_RANGE)]
energy_dict = dict()
for _ in range(N):
grid_map.append(list(map(int, input().split())))
for i in range(N):
for j in range(M):
if grid_map[i][j] > 0:
curr_status_map[MAX_RANGE//2+i][MAX_RANGE//2+j] = INACTIVE
curr_time_map[MAX_RANGE//2+i][MAX_RANGE//2+j] = grid_map[i][j]
energy_dict[(MAX_RANGE//2+i, MAX_RANGE//2+j)] = grid_map[i][j]
multiply_cells(0)
for i in range(MAX_RANGE):
for j in range(MAX_RANGE):
if curr_status_map[i][j] != DIE and curr_time_map[i][j] != NOT_EXIST:
count += 1
print("#{} {}".format(test_case+1, count))
