[코드트리] 미생물 연구 - 파이썬

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/microbial-research/description

코딩테스트 기출 문제 설명: 미생물 연구 | 코드트리

---

from collections import deque

N, Q = map(int, input().split())
# arr: 메인 배양 용기(격자)
arr = [[0] * N for _ in range(N)]
# micro_ls: Q개 미생물의 초기 투입 정보 저장
micro_ls = []
for _ in range(Q):
    micro_ls.append(list(map(int, input().split())))

# --- 기능별 함수 정의 --- 
def insert_and_process_microbes(current_arr, r1, c1, r2, c2, microbe_id):
    """
    1. 새로운 미생물을 투입하고, 잠식당한 미생물의 분열 여부를 확인 및 처리합니다.
    """
    eaten_microbes = set()
    # 새로운 미생물 투입 
    for _r in range(c1, c2):
        for _c in range(r1, r2):
            if current_arr[_r][_c] != 0:
                eaten_microbes.add(current_arr[_r][_c])
            current_arr[_r][_c] = microbe_id

    # 잠식 후 분열된 미생물 제거
    for m_id in eaten_microbes:
        remaining_cells = []
        for r in range(N):
            for c in range(N):
                if current_arr[r][c] == m_id:
                    remaining_cells.append((r, c)) # 침범당한 미생물 좌표 저장해서 분열 체크
        
        if not remaining_cells:
            continue

        # BFS로 연결된 영역 크기 확인
        q = deque([remaining_cells[0]])
        visited = {remaining_cells[0]}
        connected_count = 1
        while q:
            curr_r, curr_c = q.popleft()
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = curr_r + dr, curr_c + dc
                if 0 <= nr < N and 0 <= nc < N and current_arr[nr][nc] == m_id and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    q.append((nr, nc))
                    connected_count += 1
        
        # 연결된 영역 크기가 전체보다 작으면 분열된 것이므로 제거
        if connected_count < len(remaining_cells):
            for r_cell, c_cell in remaining_cells:
                current_arr[r_cell][c_cell] = 0
    
    return current_arr


def rearrange_microbes(current_arr):
    """
    2. 미생물들을 새 배양 용기로 규칙에 맞게 재배치합니다.
    """
    microbe_info = {} # {미생물ID: 넓이}
    for r in range(N):
        for c in range(N):
            if current_arr[r][c] != 0:
                m_id = current_arr[r][c]
                microbe_info[m_id] = microbe_info.get(m_id, 0) + 1
    
    # 넓이 내림차순, ID 오름차순으로 정렬
    sorted_microbe_ids = sorted(microbe_info.keys(), key=lambda m_id: (-microbe_info[m_id], m_id))

    new_arr = [[0] * N for _ in range(N)]
    
    for m_id in sorted_microbe_ids:
        # 미생물의 상대적 모양 추출
        cells = []
        min_r, min_c = N, N
        for r in range(N):
            for c in range(N):
                if current_arr[r][c] == m_id:
                    cells.append((r, c))
                    min_r = min(min_r, r)
                    min_c = min(min_c, c)
        shape = [(r - min_r, c - min_c) for r, c in cells] # 상대좌표로 모양만
        
        # 재배치할 최적의 위치 탐색 (x좌표 우선, 그 다음 y좌표)
        placed = False
        for place_c in range(N): # x좌표
            for place_r in range(N): # y좌표
                can_place = True
                for dr, dc in shape:
                    nr, nc = place_r + dr, place_c + dc
                    if not (0 <= nr < N and 0 <= nc < N and new_arr[nr][nc] == 0):
                        can_place = False
                        break
                
                if can_place:
                    for dr, dc in shape:
                        new_arr[place_r + dr][place_c + dc] = m_id
                    placed = True
                    break
            if placed:
                break
    
    return new_arr


def calculate_score(current_arr):
    """
    3. 재배치가 끝난 용기에서 인접한 미생물들의 점수를 계산합니다.
    """
    final_microbe_info = {} # {미생물ID: 넓이}
    for r in range(N):
        for c in range(N):
            if current_arr[r][c] != 0:
                m_id = current_arr[r][c]
                final_microbe_info[m_id] = final_microbe_info.get(m_id, 0) + 1

    adjacent_pairs = set()
    for r in range(N):
        for c in range(N):
            if current_arr[r][c] == 0:
                continue
            m_id1 = current_arr[r][c]
            # 오른쪽과 아래쪽만 확인하여 중복 방지
            for dr, dc in [(0, 1), (1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < N and 0 <= nc < N and current_arr[nr][nc] != 0 and current_arr[nr][nc] != m_id1:
                    m_id2 = current_arr[nr][nc]
                    pair = tuple(sorted((m_id1, m_id2)))
                    adjacent_pairs.add(pair)
    
    score = 0
    for m1, m2 in adjacent_pairs:
        if m1 in final_microbe_info and m2 in final_microbe_info:
            score += final_microbe_info[m1] * final_microbe_info[m2]
    
    return score


# --- 메인 실행 로직 ---
for i in range(Q):
    # i번째 실험(0-indexed)은 (i+1)번 미생물이 투입됨
    microbe_id = i + 1
    r1, c1, r2, c2 = micro_ls[i]

    # 1단계: 미생물 투입 및 분열 처리
    arr = insert_and_process_microbes(arr, r1, c1, r2, c2, microbe_id)

    # 2단계: 배양 용기 재배치
    arr = rearrange_microbes(arr)
    
    # 3단계: 점수 계산 및 출력
    score = calculate_score(arr)
    print(score)