[SWEA - 파이썬] 2382.미생물 격리

문제 보러 가기

풀이 ❄

"엄청난 알고리즘!! 을 알아야 해!!"라기 보다는 조건을 꼼꼼히 반영해서 푸는 문제였다.
나는 미생물 군집의 인덱스, 수, 이동 방향들을 리스트로 저장하고 풀었다.
M 시간 동안 아래 과정을 반복했다.
1. 이동 시키기
- 이동 방향에 맞춰서 이동시키기(이동 결과를 리스트에 반영)
2. 약품 부분으로 간 미생물 군집 처리
- 수를 절반으로
- 만약 수가 0이 되면 군집 없애기
- 방향은 반대로

- 처음에는 원래 쓰던 리스트에서 del을 해서, 수가 0이 된 미생물 군집을 처리했다. 그런데 틀렸다.. 잠깐 슬퍼하다가 생각해보니, 원래 리스트에서 del을 하면 리스트 길이가 짧아져서 끝까지 볼 수 없게 된다. 그래서 새로운 리스트(new_microbes)를 만들어서 사용했고, 과정이 끝난 후에 deepcopy로 microbes에 복사했다.

3. 겹치는 미생물 군집 처리
- 여러 군집이 만나면 수는 다 더하고, 방향은 제일 큰 군집 쪽으로
- while 두 개로 열심히 구현했다.
- 마지막 군집을 반영하지 않아서, 한번 틀렸다.. 마지막 군집 반영하는 부분을 제일 열심히 생각했던 것 같다!

M 시간이 지나고 난 후에, 미생물의 수를 출력하면 정답!!

코드 🎄

# import sys
import copy
# sys.stdin = open("../input.txt")

T = int(input())
for tc in range(1,T+1):
    N,M,K = map(int,input().split())

    # 미생물 군집 정보 저장 & 초기화
    microbes = []
    for _ in range(K):
        col, row, cnt, direct = map(int,input().split())
        microbes.append([col, row, cnt, direct])

    # M 시간 동안
    for t in range(M):
        # 미생물 쭉 보면서
        for i in range(len(microbes)):
            col, row, cnt, direct = microbes[i]
            # 이동 시키기
            if direct == 1: # 상
                microbes[i] = [col-1, row, cnt, direct]
            elif direct==2: # 하
                microbes[i] = [col+1, row, cnt, direct]
            elif direct==3: # 좌
                microbes[i] = [col, row-1, cnt, direct]
            elif direct==4: # 우
                microbes[i] = [col, row+1, cnt, direct]

        # 미생물 쭉~ 보면서
        new_microbes = []
        for i in range(len(microbes)):
            col, row, cnt, direct = microbes[i]

            # 약품 부분으로 가면 (방향- 반대로, 수 - 절반)
            if col == 0 or col == N-1 or row == 0 or row == N-1:
                cnt = int(cnt/2) # 수 절반
                if cnt == 0:
                    # 만약에 0이면 군집 없애기
                    pass
                else:
                    # 방향 반대로
                    if direct == 1 or direct==3:
                        direct += 1
                    elif direct == 2 or direct == 4:
                        direct -= 1
                    new_microbes.append([col, row, cnt, direct])
            else:
                new_microbes.append([col, row, cnt, direct])
        microbes = copy.deepcopy(new_microbes)

        # 미생물 정렬(같은 위치인지 편하게 보려고)
        microbes.sort()
        # 여러 군집이 만나면(방향 - 가장 큰 군집 방향으로, 수 - 다 더하기)
        new_microbes = []
        idx = 0
        cnt_total = 0
        direct=[-1,-1]
        flag = False

        while idx < len(microbes)-1:
            cnt_total = microbes[idx][2]
            direct = (microbes[idx][3], microbes[idx][2]) # 방향, 수

            while True and idx < len(microbes)-1:
                if microbes[idx][0] == microbes[idx+1][0] and microbes[idx][1] == microbes[idx+1][1]: # 같은 좌표에 여러 군집
                    cnt_total += (microbes[idx+1][2])
                    if direct[1] < microbes[idx+1][2]:
                        direct = (microbes[idx+1][3], microbes[idx+1][2])
                    idx += 1
                    flag = True
                else:
                    new_microbes.append([microbes[idx][0], microbes[idx][1], cnt_total, direct[0]])
                    idx += 1
                    flag = False
                    break
        # 마지막 꺼 반영
        if flag == False:
            new_microbes.append([microbes[idx][0], microbes[idx][1], microbes[idx][2], microbes[idx][3]])
        else:
            new_microbes.append([microbes[idx][0], microbes[idx][1], cnt_total, direct[0]])

        microbes = copy.deepcopy(new_microbes)
    # print([c for a, b, c, d in microbes])
    print(f'#{tc} {sum([c for a, b, c, d in microbes])}')