미생물배양

이문제를 분석하고 있는데 아직 pass못했음 문제가 거의 맞느네 ..
좋아요! 이번에는 문제 분석 → 풀이 기획 → 구현 원리를 단계별로 아주 자세하게 정리해 드리겠습니다.

---

1️⃣ 문제 분석

문제 핵심

• N x N 배양 용기에 미생물 블록을 여러 번 투입하고, 특정 규칙으로 재배치 후 성과 점수를 계산하는 문제
• 블록 투입, 겹침 처리, 쪼개짐 판단, 재배치, 점수 계산 총 3단계로 나눌 수 있음

문제 조건

1. 블록 투입
   • 좌표 (r1, c1) ~ (r2, c2) 직사각형 형태
   • 새 블록이 기존 블록과 겹치면 기존 블록의 겹친 부분만 제거
   • 기존 블록이 2개 이상 영역으로 나누어지면 전체 제거
2. 재배치
   • 블록 크기 순으로 큰 것부터 배치
   • 같은 크기면 ID 순서
   • 좌표가 작은 곳부터 배치, 배치 불가 시 제거
   • 블록 형태 유지
3. 점수 계산
   • 인접 블록 쌍마다 (영역 넓이 곱) 합
   • 중복 쌍은 계산하지 않음

제한

• N ≤ 15, Q ≤ 50 → brute-force 탐색 가능
• 좌표 시작은 좌측 하단 (0,0)

---

2️⃣ 풀이 기획

Step 1: 데이터 구조

• Block 클래스 정의
  • ID, 셀 리스트 (cells), 최소/최대 좌표 (min_r, min_c, max_r, max_c)
  • 함수:
    • update_bounds() : 셀 리스트 기준 경계 갱신
    • size() : 블록 크기
    • remove_cells(cells_to_remove) : 블록 일부 제거
    • is_split() : 블록이 쪼개졌는지 판단
• 그리드: 2D 배열, 각 셀 값 = 블록 ID
• 블록 리스트: 모든 블록 객체 관리

---

Step 2: 블록 투입 전략

1. 새 블록의 셀 좌표 리스트 생성
2. 기존 블록과 겹치는 부분 제거 (remove_cells)
3. 겹친 후 기존 블록이 쪼개졌는지 검사
   • 쪼개진 블록은 삭제
4. 새 블록을 블록 리스트에 추가
5. 그리드 갱신

핵심: BFS/DFS를 쓰지 않고 블록의 셀 리스트만으로 쪼개짐 판단 가능.
겹치는 셀 제거 후, 남은 셀이 연속인지 확인하면 됨.

---

Step 3: 블록 재배치

1. 블록 크기 내림차순 → ID 오름차순 정렬
2. 새 2D 그리드 생성
3. 각 블록 순회
   • 블록 좌표 → (0,0) 기준 상대 좌표로 변환
   • 가능한 위치 탐색
     • 좌측 하단부터 우측 상단까지
     • 겹침 없는지 확인
     • 불가능 → 블록 제거
4. 배치 가능하면 절대 좌표 갱신, 그리드 갱신

핵심: 블록 배치 시 절대 좌표 → 상대 좌표 변환으로 위치 계산이 편해짐

---

Step 4: 점수 계산

1. 블록 ID → 셀 좌표 맵 생성
2. 각 블록 셀에서 상하좌우 탐색
   • 다른 블록이 인접하면 adjacency 기록
3. 중복 제거
4. (인접 블록 넓이 곱) 계산

핵심: 단순 x,y 스퀘어 넓이 계산이 아니라 인접 블록 쌍별로 실제 영역 곱 계산

---

3️⃣ 구현 원리

Block 클래스

• 셀 리스트 관리 → 기존 BFS/DFS 없이 블록 영역 판단
• 쪼개짐 판단 → 제거 후 남은 셀 연속 여부 확인
• 재배치 편리 → 상대 좌표 변환으로 새로운 위치 계산

그리드

• 투입 → 겹침 제거 → 재배치 → 점수 계산 흐름에서 단일 원본 그리드 유지
• 배치 후 새 그리드 생성 → 기존 그리드 교체

점수 계산

• 블록 단위로 인접 블록 확인 → 영역 넓이 곱 계산
• 중복 쌍 제거 → set 사용

---

4️⃣ 전체 흐름 요약

1. 입력 처리
   • N, Q, 블록 좌표 읽기
2. 실험 반복
   • insert_block() : 새 블록 투입 → 겹친 블록 처리 → 쪼개짐 제거 → 그리드 갱신
   • move_blocks() : 블록 크기 기준 재배치 → 위치 갱신
   • calculate_score() : 인접 블록 쌍 → 넓이 곱 → 합산 → 출력
3. 최종 결과
   • 각 실험별 점수 출력

---

이 구조의 장점:

• Block 클래스 기반 → 영역, 셀, 좌표 정보를 한 곳에서 관리
• BFS/DFS 최소화 → 겹침/쪼개짐 판단 효율적
• 재배치/점수 계산 모듈화 → 유지보수 용이
• 제한 조건(N ≤ 15, Q ≤ 50)에 적합한 구현

---

원하면 제가 실제 예제 입력을 가지고 블록별 셀과 그리드 상태 변화를 시각화해서
각 단계에서 블록이 어떻게 겹치고 제거되며 재배치되는지 보여드릴 수도 있습니다.

그렇게 해드릴까요?

좋아요! 위 코드를 실행 순서대로 단계별로 아주 자세하게 설명해 드리겠습니다.

---

1️⃣ 프로그램 시작 (main())

N,Q = map(int,input().split())
sim = MicroSimulation(N)

• 입력으로 그리드 크기 N과 실험 횟수 Q를 받음
• MicroSimulation 객체 생성 → 내부적으로:
  • self.grid : NxN 그리드 생성, 초기값 0
  • self.blocks : 빈 리스트, 블록들을 관리
  • self.next_id : 새 블록 ID 초기화 1

---

2️⃣ 실험 반복 (for _ in range(Q))

매 실험마다 다음 과정을 수행합니다.

r1,c1,r2,c2 = map(int,input().split())
sim.insert_block(r1,c1,r2,c2)
sim.move_blocks()
print(sim.calculate_score())

---

3️⃣ 블록 투입 (insert_block)

3-1. 새 블록 생성

new_cells = [(r,c) for r in range(r1,r2) for c in range(c1,c2)]
new_block = Block(self.next_id, new_cells)
self.next_id += 1

• 입력받은 좌표 (r1,c1) ~ (r2,c2)로 셀 좌표 리스트 생성
• Block 객체 생성 → 내부에서 update_bounds()로 최소/최대 좌표 계산
• 블록 ID 증가

3-2. 기존 블록과 겹치는 셀 제거

for blk in self.blocks:
    overlapping = [cell for cell in blk.cells if cell in new_cells]
    if overlapping:
        blk.remove_cells(overlapping)

• 모든 기존 블록 순회
• 새 블록과 겹치는 셀만 제거
• remove_cells → 제거 후 update_bounds()로 경계 갱신

3-3. 쪼개진 블록 제거

self.blocks = [blk for blk in self.blocks if not blk.is_split()]

• is_split() 함수로 블록이 쪼개졌는지 판단
• 쪼개진 블록은 리스트에서 삭제

3-4. 새 블록 추가 및 그리드 갱신

self.blocks.append(new_block)
self.update_grid()

• 새 블록을 블록 리스트에 추가
• update_grid() → 블록 리스트 기준으로 2D 그리드 갱신

---

4️⃣ 블록 재배치 (move_blocks)

4-1. 블록 정렬

self.blocks.sort(key=lambda b: (-b.size(), b.id))

• 블록 크기 내림차순 → 큰 블록 먼저 배치
• 블록 크기가 같으면 ID 오름차순

4-2. 새로운 그리드 준비

new_grid = [[0]*self.N for _ in range(self.N)]

• 재배치 후의 새 그리드 생성
• 모든 셀 0으로 초기화

4-3. 블록 배치

for blk in self.blocks:
    placed = False
    shape = blk.cells
    # 상대좌표 변환 (0,0 기준)
    min_r = min(r for r,c in shape)
    min_c = min(c for r,c in shape)
    rel_cells = [(r-min_r, c-min_c) for r,c in shape]

• 블록의 절대좌표를 상대좌표로 변환
• (0,0) 기준으로 셀 위치 계산
• 배치 가능한 위치 탐색

4-4. 위치 탐색 및 배치

for r0 in range(self.N - max_r):
    for c0 in range(self.N - max_c):
        if all(new_grid[r0+rr][c0+cc]==0 for rr,cc in rel_cells):
            # 배치
            for rr,cc in rel_cells:
                new_grid[r0+rr][c0+cc] = blk.id
            blk.cells = [(r0+rr, c0+cc) for rr,cc in rel_cells]
            blk.update_bounds()
            placed = True
            break
    if placed: break

• (r0, c0)를 블록 배치의 시작점으로 가정
• 모든 상대좌표 셀이 새 그리드에서 비어있으면 배치 가능
• 절대좌표 갱신 → 블록의 cells와 update_bounds()

4-5. 새 그리드로 교체

self.grid = new_grid

• 배치가 끝난 후, 기존 그리드를 새 그리드로 교체

---

5️⃣ 점수 계산 (calculate_score)

5-1. 인접 블록 기록

adjacency = {blk.id:set() for blk in self.blocks}
directions = [(0,1),(1,0),(0,-1),(-1,0)]
block_map = {(r,c): blk.id for blk in self.blocks for r,c in blk.cells}

• 각 블록의 인접 블록을 기록할 adjacency 딕셔너리 생성
• 상하좌우 탐색 방향
• 좌표 → 블록 ID 맵 생성

for blk in self.blocks:
    for r,c in blk.cells:
        for dr,dc in directions:
            nr,nc = r+dr, c+dc
            if 0<=nr<self.N and 0<=nc<self.N:
                other_id = block_map.get((nr,nc),0)
                if other_id!=0 and other_id!=blk.id:
                    adjacency[blk.id].add(other_id)

• 각 셀에서 상하좌우 탐색 → 인접 블록 ID 추가
• 중복 블록 제외, 자기 자신 제외

5-2. 점수 계산

sizes = {blk.id: blk.size() for blk in self.blocks}
score = 0
counted = set()
for a in adjacency:
    for b in adjacency[a]:
        if (a,b) in counted or (b,a) in counted:
            continue
        score += sizes[a]*sizes[b]
        counted.add((a,b))

• 블록 ID → 크기 맵 생성
• 인접 블록 쌍마다 크기 곱 계산
• (a,b) 쌍 중복 계산 방지

5-3. 점수 반환

return score

• 최종 점수 반환 → main()에서 출력

---

✅ 실행 흐름 요약

1. 입력받은 N, Q → MicroSimulation 객체 생성
2. Q번 반복:
   • 새 블록 생성 → 기존 블록 겹침 제거 → 쪼개진 블록 삭제 → 그리드 갱신
   • 블록 크기 내림차순 → 새 그리드에 재배치 → 블록 좌표 갱신
   • 인접 블록 쌍 확인 → 크기 곱 계산 → 점수 출력

---

즉, 블록 투입 → 겹침 처리 → 쪼개짐 제거 → 재배치 → 점수 계산 순으로 체계적으로 진행됩니다.

원하면 제가 실제 예제 입력을 가지고 각 단계별 블록과 그리드 상태를 시각화해서 보여줄 수도 있습니다.
그렇게 해드릴까요?

 

# 미생물 블록 시뮬레이션

# 블록 클래스 정의
class Block:
    def __init__(self, block_id, cells):
        self.id = block_id  # 블록 ID
        self.cells = cells  # 블록을 구성하는 셀 리스트 [(r,c), ...]
        self.update_bounds()  # 좌하단, 우상단 좌표 계산

    def update_bounds(self):
        """블록의 좌하단과 우상단 좌표 계산"""
        if not self.cells:  # 셀이 없으면 모두 0
            self.min_r = self.min_c = self.max_r = self.max_c = 0
            return
        self.min_r = min(r for r,c in self.cells)  # 최소 행
        self.min_c = min(c for r,c in self.cells)  # 최소 열
        self.max_r = max(r for r,c in self.cells)  # 최대 행
        self.max_c = max(c for r,c in self.cells)  # 최대 열

    def size(self):
        """블록의 셀 개수 반환"""
        return len(self.cells)

    def overlaps(self, other):
        """다른 블록과 겹치는지 확인"""
        return any((r,c) in other.cells for r,c in self.cells)

    def remove_cells(self, cells_to_remove):
        """특정 셀들을 제거하고 블록 갱신"""
        self.cells = [cell for cell in self.cells if cell not in cells_to_remove]
        self.update_bounds()  # 제거 후 경계 갱신

    def is_split(self):
        """블록이 쪼개졌는지 판단 (연속된 스퀘어 여부)"""
        if not self.cells:  # 셀이 없으면 쪼개진 것
            return True
        grid = set(self.cells)
        min_r = self.min_r
        max_r = self.max_r
        # 각 줄에 블록 셀 존재 여부 체크
        prev_row_cells = None
        for r in range(min_r, max_r+1):
            row_cells = [c for rr, c in self.cells if rr==r]  # 현재 행의 컬럼 위치
            row_cells.sort()
            if not row_cells:  # 빈 줄이 있으면 split
                return True
            if prev_row_cells is not None:
                # 두 줄의 컬럼이 하나라도 겹치면 계속 연결
                if max(prev_row_cells) < min(row_cells) or min(prev_row_cells) > max(row_cells):
                    return True
            prev_row_cells = row_cells
        return False

# 시뮬레이션 클래스
class MicroSimulation:
    def __init__(self, N):
        self.N = N  # 그리드 크기
        self.grid = [[0]*N for _ in range(N)]  # 초기 그리드
        self.blocks = []  # 블록 객체 리스트
        self.next_id = 1  # 새 블록 ID

    def insert_block(self, r1, c1, r2, c2):
        """새 블록 투입 및 기존 블록 겹치는 부분 처리"""
        new_cells = []
        # 새 블록 영역 설정
        for r in range(r1, r2):
            for c in range(c1, c2):
                new_cells.append((r,c))
        new_block = Block(self.next_id, new_cells)  # 새 블록 객체 생성
        self.next_id += 1  # ID 증가

        # 기존 블록 겹치는 셀 제거
        for blk in self.blocks:
            overlapping = [cell for cell in blk.cells if cell in new_cells]
            if overlapping:
                blk.remove_cells(overlapping)
        # 쪼개진 블록 제거
        self.blocks = [blk for blk in self.blocks if not blk.is_split()]

        # 새 블록 추가
        self.blocks.append(new_block)

        # 그리드 갱신
        self.update_grid()

    def update_grid(self):
        """그리드 상태를 블록 리스트 기준으로 갱신"""
        self.grid = [[0]*self.N for _ in range(self.N)]  # 초기화
        for blk in self.blocks:
            for r,c in blk.cells:
                self.grid[r][c] = blk.id

    def move_blocks(self):
        """큰 블록 순서대로 재배치"""
        # 블록 크기 기준 내림차순, ID 오름차순
        self.blocks.sort(key=lambda b: (-b.size(), b.id))
        new_grid = [[0]*self.N for _ in range(self.N)]

        for blk in self.blocks:
            placed = False
            shape = blk.cells
            # 상대 좌표 기준 (0,0)
            min_r = min(r for r,c in shape)
            min_c = min(c for r,c in shape)
            rel_cells = [(r - min_r, c - min_c) for r,c in shape]  # 상대 좌표
            max_r = max(r for r,c in rel_cells)
            max_c = max(c for r,c in rel_cells)

            # 배치 가능한 좌표 탐색
            for r0 in range(self.N - max_r):
                for c0 in range(self.N - max_c):
                    # 겹치는지 확인
                    if all(new_grid[r0+rr][c0+cc]==0 for rr,cc in rel_cells):
                        # 배치
                        for rr,cc in rel_cells:
                            new_grid[r0+rr][c0+cc] = blk.id
                        # 절대좌표 갱신
                        blk.cells = [(r0+rr, c0+cc) for rr,cc in rel_cells]
                        blk.update_bounds()
                        placed = True
                        break
                if placed: break
        self.grid = new_grid  # 새 그리드로 교체

    def calculate_score(self):
        """인접 블록 간 점수 계산"""
        adjacency = {blk.id:set() for blk in self.blocks}  # 인접 블록 기록
        directions = [(0,1),(1,0),(0,-1),(-1,0)]  # 상하좌우
        block_map = {}
        for blk in self.blocks:
            for r,c in blk.cells:
                block_map[(r,c)] = blk.id  # 좌표→블록ID 맵

        # 인접 블록 기록
        for blk in self.blocks:
            for r,c in blk.cells:
                for dr,dc in directions:
                    nr, nc = r+dr, c+dc
                    if 0<=nr<self.N and 0<=nc<self.N:
                        other_id = block_map.get((nr,nc),0)
                        if other_id!=0 and other_id!=blk.id:
                            adjacency[blk.id].add(other_id)

        # 점수 계산, 중복 제거
        sizes = {blk.id: blk.size() for blk in self.blocks}  # 블록 크기
        score = 0
        counted = set()  # 중복 방지
        for a in adjacency:
            for b in adjacency[a]:
                if (a,b) in counted or (b,a) in counted:
                    continue
                score += sizes[a]*sizes[b]  # 점수 = 크기 곱
                counted.add((a,b))
        return score

# 입력 처리 및 시뮬레이션 실행
def main():
    N,Q = map(int,input().split())  # 그리드 크기 N, 실험 횟수 Q
    sim = MicroSimulation(N)  # 시뮬레이션 객체 생성
    for _ in range(Q):
        r1,c1,r2,c2 = map(int,input().split())  # 블록 좌하, 우상 좌표
        sim.insert_block(r1,c1,r2,c2)  # 새 블록 투입
        sim.move_blocks()  # 블록 재배치
        print(sim.calculate_score())  # 점수 출력

if __name__ == "__main__":
    main()