SW Expert Academy - 줄기세포배양 (python)

❓ 문제 - SW Expert Academy - 줄기세포배양 - python 풀이법

 

출처 

(https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo)

 

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 줄기세포의 배양이 무대한 커질 수 있기 때문에 리스트이 범위는 행(0 ~ n+k*2+1), 열(0 ~ m+k*2+1)로 잡고 생명력의 정보를 담을 live(만약 죽은 세포는 -1로표현, 0은 아무것도 안 담긴 상태), 활성과 비활성 상태를 표시할 check 리스트(양수에는 활성화 상태, 음수에는 비활성 상태, 0은 아무 것도 안 담기거나 죽은 상태)를 활용한다. check 리스트에서 만약 세포가 비활성 상태라면 비활성 지속 기간을 처음 세포가 생겼을 때의 생명력에 -해주고, 시간이 흐르면서 check를 +1해주고, 비활성에서 활성상태로 넘어가면 해당 위치의 생명력을 양수값으로 변경한다.
• 시간에 따라 번식한 줄기세포의 정보를 담을 l리스트를 선언해주고,  모든 행과 열을 돌면서 만약 죽은 상태가 아니거나 아무것도 없는 상태가 아닐 때, 비활성상태인지를 확인한다(비활성 상태 - 음수값). 만약 비활성 값이 -1이라면 다음엔 활성상태로 변경해줘야 하므로 양수의 생명력 값으로 변경해주고, -1보다 작은 값이라면 비활성 상태를 줄여주기 위해 +1 해준다.
• 만약 해당 위치가 죽은 상태가 아니거나 아무것도 없는 상태가 아니면서 활성상태라면 4방향으로 탐색해서 죽거나 원래 세포가 존재하는 곳이 아닌 곳을 찾아 그곳에 아무것도 존재하지 않는다면 해당 곳에 생명력값을 넣어주고 비활성상태로 만들어준다. 죽은세포나 원래 세포가 존재하진 않지만 새로운 세포가 있는 곳이라면 생명력을 비교해서 생명력이 크다면 변경해준다.
• 그리고 4방향으로 번식한 후, 활성상태가 1이라면 다음은 죽은 세포로 변경되므로 값을 live에 죽은세포(-1) 값, check에 죽은 세포(0)으로 변경해준다.
• 모든 행과 열을 돌아서 세포 번식 한 정보를 담은 l 리스트로 기존 생명력을 담은 live에 갱신해준다.
• k번의 세포 번식이 끝난 후 check 상태를 돌아서 0이 아닌 값을 카운트(활성, 비활성세포) 후 정답을 출력한다.

2. 문제 풀면서 느낀점

• 세포번식으로 세포 상태를 체크할 갯수가 계속 증가해서 처음에 n, m, k의 최대 범위를 고려해서 이중리스트를 650 * 650 으로 잡고 구현하였는데 너무 시간이 오래걸려서 (n+2*k+2), (m+2*k+2)로 수정했다. 리스트의 행과 열을 입력 데이터의 값을 기준으로 선언하자....
• 세포가 번식하는 것을 또한 4방향으로 탐색하는데, 시작 점을 중심으로 잡고 번식하기에 인덱스 고려할 게 너무 많아서 걍 0 행, 0열에 초기 세포상태 저장하고 0, n+2*k+1 인 행을 연결하고, 0, m+2*k+1 인 열을 연결시켜서 처리했다...
• 삼성 역테 풀 때 항상 시간을 고려해야하며 출력 상태는 print(f'#{test_case} {cnt}') 로 해야한다..

 

💻 소스코드

# SWEA - 줄기세포배양
# 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

T = int(input())
for test_case in range(1, 1+T):
    n, m, k = map(int, input().split())
    live = [[0]*(m+2*k+2) for _ in range(n+2*k+2)]
    check = [[0]*(m+2*k+2) for _ in range(n+2*k+2)]
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(m):
            live[i][j] = data[j]
            if data[j] > 0:
                check[i][j] = -(data[j])

    for _ in range(k):
        l = [[0]*(m+2*k+2) for _ in range(n+2*k+2)]
        for i in range(n+2*k+2):
            for j in range(m+2*k+2):
                if live[i][j] == 0 or live[i][j] == -1:
                    continue
                if check[i][j] < 0:
                    if check[i][j] == -1:
                        check[i][j] = live[i][j]
                    else:
                        check[i][j] += 1
                elif check[i][j] > 0:
                    x, y = i, j
                    for p in range(4):
                        nx = (x+dx[p]) % (n+k*2+2)
                        ny = (y+dy[p]) % (m+k*2+2)
                        if live[nx][ny] == -1 or live[nx][ny] > 0:
                            continue
                        if l[nx][ny] == 0:
                            l[nx][ny] = live[x][y]
                            check[nx][ny] = -live[x][y]
                        elif l[nx][ny] < live[x][y]:
                            l[nx][ny] = live[x][y]
                            check[nx][ny] = -live[x][y]
                    if check[i][j] == 1:
                        live[i][j] = -1
                        check[i][j] = 0
                    else:
                        check[i][j] -= 1

        for i in range(n+2*k+2):
            for j in range(m+2*k+2):
                if l[i][j] > 0 and live[i][j] == 0:
                    live[i][j] = l[i][j]

    cnt = 0
    for i in range(n+2*k+2):
        for j in range(m+2*k+2):
            if check[i][j] != 0:
                cnt += 1
    print(f'#{test_case} {cnt}')