[SWEA 2382번] 미생물 격리 - 파이썬(python)

SW Expert Academy

문제

정사각형 구역 안에 K개의 미생물 군집이 있다.

이 구역은 가로 N개, 세로 N개, 총 N * N 개의 동일한 크기의 정사각형 셀들로 이루어져 있다.

미생물들이 구역을 벗어나는걸 방지하기 위해, 가장 바깥쪽 가장자리 부분에 위치한 셀들에는 특수한 약품이 칠해져 있다.

① 최초 각 미생물 군집의 위치와 군집 내 미생물의 수, 이동 방향이 주어진다. 약품이 칠해진 부분에는 미생물이 배치되어 있지 않다. 이동방향은 상, 하, 좌, 우 네 방향 중 하나이다.

② 각 군집들은 1시간마다 이동방향에 있는 다음 셀로 이동한다.

③ 미생물 군집이 이동 후 약품이 칠해진 셀에 도착하면 군집 내 미생물의 절반이 죽고, 이동방향이 반대로 바뀐다.
미생물 수가 홀수인 경우 반으로 나누어 떨어지지 않으므로, 다음과 같이 정의한다.
살아남은 미생물 수 = 원래 미생물 수를 2로 나눈 후 소수점 이하를 버림 한 값
따라서 군집에 미생물이 한 마리 있는 경우 살아남은 미생물 수가 0이 되기 때문에, 군집이 사라지게 된다,

④ 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다.
합쳐 진 군집의 미생물 수는 군집들의 미생물 수의 합이며, 이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다.
합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않으므로 고려하지 않아도 된다.

M 시간 동안 이 미생물 군집들을 격리하였다. M시간 후 남아 있는 미생물 수의 총합을 구하여라.

입력

첫 줄에는 총 테스트 케이스의 개수 T가 주어진다.

그 다음 줄부터 T개의 테스트 케이스가 차례대로 주어진다.

각 테스트 케이스의 첫째 줄에는 구역의 한 변에 있는 셀의 개수 N, 격리 시간 M, 미생물 군집의 개수 K가 순서대로 주어지며, 다음 K줄에 걸쳐서 미생물 군집 K개의 정보가 주어진다.

미생물 군집의 정보는 세로 위치, 가로 위치, 미생물 수, 이동 방향 순으로 4개의 정수가 주어진다.

출력

테스트 케이스의 개수 만큼 T개의 줄에 각 테스트 케이스에 대한 답을 출력한다.

각 줄은 “#x”로 시작하고, 공백을 하나 둔 후 정답을 출력한다. (x는 테스트 케이스의 번호이며, 1번부터 시작한다.)

출력해야 할 정답은 M시간 후 남아 있는 미생물 수의 총 합이다.

풀이

• 먼저 미생물이 움직이는 것을 리스트에 갱신해야 한다.
• 따라서 방향배열(상하좌우)를 만들어서 리스트를 갱신해주었다.
• 셀의 양끝에 도착했을 경우 미생물의 수가 절반으로 줄고 방향이 반대로 변하기 때문에 이를 위한 tb를 만들어 주었다.
• 이렇게 모든 미생물 군집의 이동이 끝나면 동일한 자리에 있는 미생물 군집은 합쳐주어야 한다.
• 따라서 y축, x축, 개수 순서대로 정렬했다.
• 그러고나면 2번째줄(1번인덱스)부터 자신의 위에 있는 군집과 비교하여 좌표가 동일하다면 미생물의 수를 더해주고 자기자신을 pop한다.(개수대로 정렬하였기 때문에 위쪽이 큰 군집)
• 이동과 군집결합을 하나로 보고 끝날 때마다 시간을 -1한다.
• 마지막에 ground에 남은 미생물의 개수를 세면 풀이가 종료된다.

코드

T = int(input())
for test_case in range(1, T + 1):
    # N: 한변의 길이 M: 격리시간  K: 미생물 군집 개수
    N, M, K = map(int, input().split())
    ground = [list(map(int, input().split())) for _ in range(K)]
    # 약품처리된 곳에 도착했을 때 방향을 바꾸기 위한 배열
    tb = [0,2,1,4,3]
    directy = [0,-1,1,0,0]
    directx = [0,0,0,-1,1]

    # 격리시간을 1번씩 빼면서 풀이
    while M > 0:
        for i in range(len(ground)):
            ground[i][0] = ground[i][0]+directy[ground[i][3]]
            ground[i][1] = ground[i][1] + directx[ground[i][3]]
            if ground[i][0]==0 or ground[i][0]==N-1 or ground[i][1]==0 or ground[i][1]==N-1:
                ground[i][2] = ground[i][2]//2
                ground[i][3] = tb[ground[i][3]]
        # 동일한 좌표의 경우 합쳐주기 위해서 정렬
        ground = sorted(ground, key=lambda x: (x[0], x[1], x[2]), reverse=True)
        # 항상 자신의 윗행렬과 비교하여 같다면 위로 합치고 자신을 pop 아니면 다음으로
        temp = 1
        while 1:
            if ground[temp][0]==ground[temp-1][0] and ground[temp][1]==ground[temp-1][1]:
                ground[temp-1][2]+=ground[temp][2]
                ground.pop(temp)
            else:
                temp+=1
            if temp>=len(ground):break
        M-=1

    remain = 0
    for i in ground:
        remain+=i[2]

    print(f'#{test_case} {remain}')