문제

링크

파이프를 최대 k번 열었다 닫은 후, 감염될 수 있는 배양체 개수의 최댓값은?

• 파이프는 처음에 모두 닫혀 있음.
• 파이프는 종류별로만 여닫을 수 있음.
• 한 종류를 열어 놓은 상태에서 다른 종류를 동시에 열수 없음.

따라서 A → B → C처럼 파이프 종류를 순서대로 선택하게 되며,
이때 최대 k번 선택하여 감염되는 배양체 수를 최대화해야 한다.

예시)

입출력 예제는 이러하다.

---

이동 경로

1 → 5
1 → 2, 3
5 → 6, 7

감염된 배양체

1, 5, 2, 3, 6, 7 = 총 6개

---

이동 경로

6 → 5
5 → 4
6 → 3
3 → 7
4 → 1
1 → 2

감염된 배양체

6, 5, 4, 3, 7, 1, 2 = 총 7개

즉, 현재 감염 상태 → 파이프 종류 선택 → 새로 감염되는 배양체 계산 → 다음 선택의 반복

---

풀이방법

frozenset

감염 상태를 표현하고, 중복 상태를 자동 제거

BFS

파이프 하나를 열었을 때 감염이 퍼지는 과정(상태 전이)을 계산

완전탐색

매 턴마다 가능한 모든 파이프 개방 경우(1,2,3)를 전부 전개

---

소스코드

파이프를 개방했을 때의 모든 경우의 수를 저장하고, 감염 집합을 frozenset으로 중복 제거해가며 상태 집합을 유지하며 그중 최대 크기를 답으로 기록한다.

from collections import deque

def solution(n, infection, edges, k):
    # 그래프 구성 (배양체 간 연결 및 파이프 종류)
    tree = [[] for _ in range(n + 1)]
    for u, v, pipe in edges:
        tree[u].append((v, pipe))
        tree[v].append((u, pipe))

    def spread(infected, target_pipe):
        """target_pipe 열었을 때 감염 확장"""
        res = set(infected)
        q = deque(res)
        while q:
            curr = q.popleft()
            for nxt, pipe in tree[curr]:
                if pipe == target_pipe and nxt not in res:
                    res.add(nxt)
                    q.append(nxt)
        return frozenset(res)

    states = {frozenset([infection])}
    max_count = 1

    # 최대 k번 파이프 작동
    for _ in range(k):
        next_states = set()
        for state in states:
            max_count = max(max_count, len(state))
            for p_type in (1, 2, 3):
                next_states.add(spread(state, p_type))
        states = next_states

    # 최종 결과 최댓값 갱신
    for state in states:
        max_count = max(max_count, len(state))

    return max_count

---

생각한 것

윽