[SWEA 5653] 줄기세포배양

접근

X시간 비활성화 상태 -> X시간동안 활성화 -> 죽음, 활성화 후 1시간 동안 번식을 한다고 한다.

이를 구현하기 위해 다음과같이 접근하였다.

만약 X = 2 라고 해보자. X에 2를 곱하면 4가 되고

4초 = 초기상태

3초 = 비활성화

2초 = 활성화

1초 = 활성화 및 번식

0초 = 죽음

위와 같이 X에 2를 곱하면 X - 1이 되는 시점에 번식이 이루어진다. 이렇게 비활성화 -> 활성 -> 번식을 구현하였다. 

 

이제는 동시에 같은 곳에 번식을 하려고할 때 X가 큰 것이 오도록 해야한다. 이를 위해 X순으로 내림차순 정렬 후에 X가 큰 것부터 처리하도록 하였다. 이를 통해 먼저 처리가 되어있거나 이미 줄기세포가 있다면 continue가 진행되어 더 낮은 X는 같은 곳에 번식이 되지 못하도록 구현하였다.

 

이 문제는 2시간에 걸쳐서 풀었다. 다음과 같은 문제가 있었다.

첫 번째는 X에 2를 곱한 값을 어느 시점에 -1을 해줘야하는지를 정확히 이해하지 못했다. 문제에 주어진 예시를 통해 시뮬레이션을 하여 어느 시점에 어떻게 처리해야하는지 정확히 이해할 필요가 있다.

 

두 번째는 2차원 리스트의 크기를 몇으로 잡아야할지 지금도 모르겠다. 처음에는 1500x1500으로 했을 때 테스트 케이스는 맞았지만 실행했을 때 메모리 초과가 발생했다. 이후 리스트의 크기를 조절하면서 제출을 했을 때 380x380일 때 PASS가 되었다. 다른 사람들의 풀이를 참고했을 때 리스트의 크기가 모두 달랐다. 이 부분은 좀 더 살펴봐야겠다.

 

구현

- 줄기세포가 번식할 맵인 board를 생성한다.

- pos에는 현재 활성화 및 비활성화된 줄기세포의 위치를 저장한다.

    N, M, K = map(int, input().split())
    input_map = [list(map(int, input().split())) for _ in range(N)]
    map_size = 380
    board = [[[-1, -1] for _ in range(map_size)] for _ in range(map_size)]
    start = map_size // 2
    pos = []

- 입력받은 초기 줄기세포의 정보를 board에 X, X*2로 저장한다.

- 이후 pos에 해당 줄기세포의 X와 위치를 저장한다.

    for y in range(N):
        for x in range(M):
            if input_map[y][x] == 0:
                continue
            board[y+start][x+start][0], board[y+start][x+start][1] = input_map[y][x], input_map[y][x] * 2
            pos.append((board[y+start][x+start][0], y+start, x+start))

- K번 반복을 진행한다.

- 먼저 pos에서 줄기세포들의 위치를 X를 기준으로 내림차순 정렬한다.

- 줄기세포의 상태를 1씩 감소시키고 상태가 X - 1과 같을 때 번식이 진행되도록 한다.

- 줄기세포의 상태가 0이면 죽는 것이기 때문에 temp_pos에 저장하지 않는다.

    for k in range(K):
        temp_pos = []
        pos = sorted(pos, key= lambda x: -x[0])
        for (p, y, x) in pos:
            board[y][x][1] -= 1
            # 번식진행한다.
            if board[y][x][0] == board[y][x][1] + 1:
                spread(y, x, p, temp_pos)
            if board[y][x][1] == 0:
                continue

            temp_pos.append((p, y, x))
        pos = temp_pos

---

전체 코드

testCase = int(input())

def spread(y, x, power, temp_pos):
    global board
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if board[ny][nx][0] == -1 and board[ny][nx][1] == -1:
            board[ny][nx][0], board[ny][nx][1] = power, power * 2
            temp_pos.append((power, ny, nx))

for tc in range(testCase):
    N, M, K = map(int, input().split())
    input_map = [list(map(int, input().split())) for _ in range(N)]
    map_size = 380
    board = [[[-1, -1] for _ in range(map_size)] for _ in range(map_size)]
    start = map_size // 2
    pos = []
    for y in range(N):
        for x in range(M):
            if input_map[y][x] == 0:
                continue
            board[y+start][x+start][0], board[y+start][x+start][1] = input_map[y][x], input_map[y][x] * 2
            pos.append((board[y+start][x+start][0], y+start, x+start))

    for k in range(K):
        temp_pos = []
        pos = sorted(pos, key= lambda x: -x[0])
        for (p, y, x) in pos:
            board[y][x][1] -= 1
            if board[y][x][0] == board[y][x][1] + 1:
                spread(y, x, p, temp_pos)
            if board[y][x][1] == 0:
                continue

            temp_pos.append((p, y, x))
        pos = temp_pos

    answer = len(pos)
    print("#{} {}".format(tc+1, answer))