미생물 격리

[ramge132]

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AZC_w6Z6yygDFAQW&contestProbId=AV597vbqAH0DFAVl&probBoxId=AZDJPc6a-doDFAVs&type=PROBLEM&problemBoxTitle=1d_recommend&problemBoxCnt=2

[ramge132]

# 미생물 군집 정보를 나타내는 클래스 정의
class MicrobeGroup:
    def __init__(self, y, x, count, direction):
        self.y = y  # y 좌표
        self.x = x  # x 좌표
        self.count = count  # 미생물 수
        self.direction = direction  # 이동 방향

# 방향에 대한 정의 (상, 하, 좌, 우)
DIRECTION = {
    1: (-1, 0),  # 상: y 좌표가 1 감소
    2: (1, 0),   # 하: y 좌표가 1 증가
    3: (0, -1),  # 좌: x 좌표가 1 감소
    4: (0, 1)    # 우: x 좌표가 1 증가
}

# 반대 방향을 정의
REVERSE_DIRECTION = {
    1: 2,  # 상 -> 하
    2: 1,  # 하 -> 상
    3: 4,  # 좌 -> 우
    4: 3   # 우 -> 좌
}

# 테스트 케이스 수 입력
T = int(input().strip())  # 입력에서 테스트 케이스의 수를 읽음

for t in range(1, T+1):
    # 셀의 개수 N, 격리 시간 M, 미생물 군집 K
    N, M, K = map(int, input().strip().split())  # N, M, K를 입력에서 읽음

    # 군집 정보를 저장할 리스트
    microbes = []

    # K개의 군집 정보를 읽어 리스트에 저장
    for _ in range(K):
        y, x, count, direction = map(int, input().strip().split())
        microbes.append(MicrobeGroup(y, x, count, direction))

    # M 시간 동안 시뮬레이션 수행
    for _ in range(M):
        # 다음 위치에 대한 정보 저장
        new_positions = {}

        # 각 미생물 군집을 이동
        for microbe in microbes:
            # 현재 미생물 군집의 이동 방향에 따른 새로운 위치 계산
            dy, dx = DIRECTION[microbe.direction]
            ny, nx = microbe.y + dy, microbe.x + dx

            # 약품이 칠해진 셀로 이동한 경우
            if ny == 0 or ny == N-1 or nx == 0 or nx == N-1:
                microbe.count //= 2  # 미생물 수가 절반으로 줄어듦
                microbe.direction = REVERSE_DIRECTION[microbe.direction]  # 이동 방향이 반대가 됨

            # 새로운 위치에 미생물이 남아있으면 new_positions에 추가
            if microbe.count > 0:
                if (ny, nx) in new_positions:
                    new_positions[(ny, nx)].append(microbe)
                else:
                    new_positions[(ny, nx)] = [microbe]

            # 군집의 현재 위치를 새로운 위치로 업데이트
            microbe.y, microbe.x = ny, nx

        # 군집이 합쳐지는 경우 처리
        new_microbes = []

        for key in new_positions:
            # 같은 위치에 여러 군집이 모인 경우
            if len(new_positions[key]) > 1:
                max_count = 0
                max_direction = None
                total_count = 0

                # 군집을 합쳐 총 미생물 수와 이동 방향을 결정
                for microbe in new_positions[key]:
                    total_count += microbe.count
                    if microbe.count > max_count:
                        max_count = microbe.count
                        max_direction = microbe.direction

                # 합쳐진 군집을 새로운 리스트에 추가
                new_microbes.append(MicrobeGroup(key[0], key[1], total_count, max_direction))
            else:
                # 군집이 하나만 있는 경우 그대로 추가
                new_microbes.append(new_positions[key][0])

        # 새로운 군집 리스트로 업데이트
        microbes = new_microbes

    # 최종 남아 있는 미생물 수의 총합 계산
    total_microbes = sum(microbe.count for microbe in microbes)

    # 결과 출력
    print(f"#{t} {total_microbes}")

[Yeonri]

import sys
sys.stdin = open('미생물격리.txt', 'r')

# 상 하 좌 우
DXY = [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]

def del_info(i):
    global lst
    lst[i][0] = float('inf')
    lst[i][1] = float('inf')
    lst[i][2] = 0
    lst[i][3] = 0
    return

def dxy(idx):
    if idx == 1:
        return DXY[0]
    if idx == 2:
        return DXY[1]
    if idx == 3:
        return DXY[2]
    if idx == 4:
        return DXY[3]
    else:
        return DXY[4]

def turn(idx):
    if idx == 1:
        return 2
    if idx == 2:
        return 1
    if idx == 3:
        return 4
    if idx == 4:
        return 3
    else:
        return 0

T = int(input())

for test_case in range(1, T + 1):
    N, M, K = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(K)]
    count = 0
    result = 0
    # M 시간 후, 남아있는 미생물들의 수
    # 미생물들이 만나면, 값을 더한 후, 더 큰 값을 가졌던 군집의 방향으로 이동한다.

    del_set = set()

    while True:
        # print(count)
        if count == M:
            for i in range(len(lst)):
                result += lst[i][2]
            break

        # 이동과 방향 설정
        for i in range(len(lst)):
            x, y = lst[i][0], lst[i][1]
            dx, dy = dxy(lst[i][3])
            nx, ny = x + dx, y + dy

            lst[i][0], lst[i][1] = nx, ny

            # 벽을 만나면 반대 방향으로 변경
            if nx == 0 or ny == 0 or nx == N - 1 or ny == N - 1:
                lst[i][3] = turn(lst[i][3])
                lst[i][2] = lst[i][2] // 2

        for i in range(len(lst) - 1):
            for j in range(i + 1, len(lst)):
                if i in del_set or j in del_set: continue
                if lst[i][0] != lst[j][0] or lst[i][1] != lst[j][1]: continue
                if lst[i][2] > lst[j][2]:
                    lst[i][2] += lst[j][2]
                    del_info(j)
                    del_set.add(j)

                else:
                    lst[j][2] += lst[i][2]
                    del_info(i)
                    del_set.add(i)

        count += 1

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

[seokbangguri]

# import sys
# sys.stdin = open('input.txt')

# 정지 상 하 좌 우 [x, y]
dxy = [[0, 0], [0, -1], [0, 1], [-1, 0], [1, 0]]

def microbe_moves(microbes, times):
    global m
    if times == m:
        return

    # 군집 이동시키기
    for i, x in enumerate(microbes):
        # 비활성화 된 군집은 건너뜀
        if x[-1] == 0:
            continue

        microbes[i][1] += dxy[x[3]][0]
        microbes[i][0] += dxy[x[3]][1]

        # 가장자리 군집 절반으로 줄이기 및 방향 바꾸기
        if microbes[i][1] == 0 or microbes[i][1] == n - 1 or microbes[i][0] == 0 or microbes[i][0] == n - 1:
            # 방향이 홀수 인 경우
            if microbes[i][3]%2:
                microbes[i][3] += 1
            # 짝수 인 경우
            else:
                microbes[i][3] -= 1

            # 개채 수 줄이기
            microbes[i][2] = int(microbes[i][2] / 2)

    # 같은 셀에 위치 시 미생물 수 합치고 가장 큰 군집의 이동방향 따르기
    find_same_pos = {}
    for idx, microbe in enumerate(microbes):
        # 비활성화 된 군집은 건너뜀
        if microbe[-1] == 0:
            continue

        pos_to_str = tuple(microbe[:2])
        if pos_to_str in find_same_pos:
            find_same_pos[pos_to_str].append(microbe + [idx])
        else:
            find_same_pos[pos_to_str] = [microbe + [idx]]

    # 같은 셀에 있는 군집들 중 가장 군집이 많은 리스트에 남은 군집들 추가하고 남은 군집들 비활성화
    for value in find_same_pos.values():
        if len(value) > 1:
            max_index = max(range(len(value)), key=lambda i: value[i][2])
            max_value_list = value[max_index]

            # 나머지 리스트들의 인덱스 2의 값을 가장 큰 값을 가진 리스트의 인덱스 2의 값에 더하고 비활성화
            for i, row in enumerate(value):
                if i != max_index:
                    microbes[max_value_list[-1]][2] += row[2]
                    microbes[row[-1]][-1] = 0

    microbe_moves(microbes, times + 1)

T = int(input())
for test_case in range(1, T + 1):
    # 셀의 한 변, 시간, 군집 개수
    n, m, k = map(int, input().split())
    # [1] <= 합체 여부
    microbes = [list(map(int, input().split())) + [1] for _ in range(k)]

    microbe_moves(microbes, 0)
    result = 0
    for i in microbes:
        if i[-1] == 0:
            continue

        result += i[2]
    print(f'#{test_case} {result}')

[happypildo]

## 미생물 격리 문제
DIRECTION = {
    1: [-1, 0],
    2: [1, 0],
    3: [0, -1],
    4: [0, 1]
}

def change_direction(in_direction):
    if in_direction == 1:
        return 2
    elif in_direction == 2:
        return 1
    elif in_direction == 3:
        return 4
    else:
        return 3

class Cluster:
    def __init__(self, N, x, y, num_of_microbe, direction):
        self.map_size = N
        self.location_x = x
        self.location_y = y
        self.num_of_microbe = num_of_microbe
        self.direction = direction
        self.is_alive = True

    def move_cluster(self):
        dx, dy = DIRECTION[self.direction]

        self.location_x = self.location_x + dx
        self.location_y = self.location_y + dy

        if self.location_x < 1 or self.location_x > self.map_size - 2:
            self.num_of_microbe = int(self.num_of_microbe / 2)
            self.direction = change_direction(self.direction)
        elif self.location_y < 1 or self.location_y > self.map_size - 2:
            self.num_of_microbe = int(self.num_of_microbe / 2)
            self.direction = change_direction(self.direction)

        if self.num_of_microbe == 0:
            self.is_alive = False

def merge_cluster(clusters):
    new_cluster = Cluster(
        N=clusters[0].map_size,
        x=clusters[0].location_x,
        y=clusters[0].location_y,
        num_of_microbe=clusters[0].num_of_microbe,
        direction=0
    )

    num_of_microbe_for_each_cluster = [c.num_of_microbe for c in clusters]

    max_idx = num_of_microbe_for_each_cluster.index(max(num_of_microbe_for_each_cluster))

    new_cluster.num_of_microbe = sum(num_of_microbe_for_each_cluster)
    new_cluster.direction = clusters[max_idx].direction

    return new_cluster

# main
T = int(input())

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

    cluster_lists = []
    for k_iter in range(K):
        x, y, num_of_microbe, direction = list(map(int, input().split()))
        cluster_lists.append(Cluster(N=N, x=x, y=y, num_of_microbe=num_of_microbe, direction=direction))

    for m_iter in range(M):
        loc_of_clusters = []

        # 군집 이동 후 위치 저장
        for idx, cluster in enumerate(cluster_lists):
            cluster.move_cluster()
            loc_of_clusters.append("000"+str(cluster.location_x)+"_"+str(cluster.location_y)+"000")

            # if not cluster.is_alive:
            #     del cluster_lists[idx]
            #     del loc_of_clusters[idx]

        # 저장된 위치 기반 동일한 위치 추출
        loc_dict = {loc: [] for loc in loc_of_clusters}
        for idx, loc in enumerate(loc_of_clusters):
            loc_dict[loc].append(idx)

        # 동일한 위치에 있는 군집 합치기
        temp_cluster_lists = []
        for dict_idx, loc_dict_key in enumerate(loc_dict.keys()):
            if len(loc_dict[loc_dict_key]) > 1:
                clusters_to_merge = []
                for idx in loc_dict[loc_dict_key]:
                    clusters_to_merge.append(cluster_lists[idx])

                temp_cluster_lists.append(merge_cluster(clusters_to_merge))
            else:
                for idx in loc_dict[loc_dict_key]:
                    temp_cluster_lists.append(cluster_lists[idx])

        cluster_lists = temp_cluster_lists

    sum_of_microbe = 0
    for cluster in cluster_lists:
        sum_of_microbe = sum_of_microbe + cluster.num_of_microbe

    print(f"#{t_iter} {sum_of_microbe}")

[Yeonri]

import sys
sys.stdin = open('미생물격리.txt', 'r')

# 상 하 좌 우
DXY = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)]

def turn(idx):
    if idx == 1:
        return 2
    if idx == 2:
        return 1
    if idx == 3:
        return 4
    if idx == 4:
        return 3

T = int(input())

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

    microb_dict = {}
    count = 0
    total = 0

    for _ in range(K): # 미생물의 개수 만큼
        x, y, num, dir = map(int, input().split())
        microb_dict.setdefault((x, y), []).append((num, dir))

    while count < M:
        count += 1
        tmp_dict = {}

        for (x, y), microb_lst in microb_dict.items():

            # microb에 존재하는 미생물들의 개수를 비교
            # 군집이 더 큰 쪽의 이동으로 변경한다.
            max_num = 0
            max_dir = 0

            # 방향을 바꿀 필요 없이 제일 큰 값만 찾아서 더해주면 된다.
            for num, dir in microb_lst:
                if num > max_num:
                    max_num = num
                    max_dir = dir

            total_num = sum(microb[0] for microb in microb_lst)
            dx, dy = DXY[max_dir]
            nx, ny = x + dx, y + dy

            if 0 == nx or N - 1 == nx or 0 == ny or N - 1 == ny:
                total_num //= 2
                max_dir = turn(max_dir)

            tmp_dict.setdefault((nx, ny), []).append((total_num, max_dir))

        microb_dict = tmp_dict

    total = sum(microb[0] for group in microb_dict.values() for microb in group)

    # for (x, y), microb_lst in microb_dict:
    #     for microb in microb_lst:
    #         e, dir = microb
    #         total += e

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