프로그래머스

프로그래머스 바이러스 파이프 풀이: 파이프 순서 DFS와 감염 BFS

작성자: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 바이러스 파이프
  • 출처: 프로그래머스, 2025 카카오 하반기 1차
  • 자체 판단 난이도: Level 4

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

n개의 배양체가 n - 1개의 파이프로 연결되어 하나의 트리를 이룹니다. 파이프는 A, B, C 세 종류 중 하나이며 처음에는 모두 닫혀 있습니다.

한 번의 행동에서는 한 종류의 파이프를 모두 열었다가 닫을 수 있습니다. 열린 동안 감염된 배양체와 연결된 배양체로 바이러스가 퍼지고, 파이프를 닫아도 이미 감염된 상태는 유지됩니다. 이 행동을 최대 k번 수행했을 때 감염시킬 수 있는 배양체 수의 최댓값을 구합니다.

같은 종류의 파이프를 다시 여는 것은 새로운 감염을 만들지 못하므로, 효과가 있는 행동은 A, B, C를 각각 최대 한 번씩 여는 것입니다. 따라서 k가 3보다 커도 실제로 탐색할 의미 있는 종류의 순서는 최대 3개입니다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

DFS로 파이프 종류의 순서 탐색

각 행동에서 선택할 수 있는 파이프 종류는 1, 2, 3입니다. 이미 사용한 종류를 used_types에 기록하고, 아직 사용하지 않은 종류를 다음 선택으로 넘기며 DFS를 수행합니다.

행동 횟수는 k를 넘을 수 없고, 세 종류를 모두 사용하면 더 확장할 필요가 없습니다. 같은 종류를 반복해도 결과가 바뀌지 않으므로 중복 순열을 탐색하지 않습니다.

BFS로 한 종류의 파이프를 통한 감염 확산

특정 파이프 종류를 열었을 때는 해당 종류의 간선만 사용할 수 있습니다. 현재 감염된 모든 노드를 큐에 넣고, 같은 타입의 파이프를 따라 이동하면서 새 노드를 감염시킵니다.

감염 집합은 행동 사이에도 유지됩니다. 따라서 BFS가 끝난 뒤 얻은 감염 집합을 다음 DFS 단계로 전달합니다.

상태 복사와 가지치기

DFS의 각 가지는 서로 다른 파이프 순서를 의미하므로, 한 가지에서 바뀐 감염 상태가 다른 가지에 영향을 주면 안 됩니다. Python의 set.copy()로 현재 상태를 복사해 다음 단계에 전달합니다.

이미 모든 n개가 감염됐다면 더 탐색할 필요 없이 바로 최댓값을 갱신할 수 있습니다.

복잡도

파이프 종류가 3개뿐이므로 서로 다른 종류 순서는 최대 1 + 3 + 3×2 + 3×2×1 = 16개입니다. 각 단계에서 BFS는 트리의 노드와 간선을 한 번씩 확인하므로 전체 시간 복잡도는 O(16n), 파이프 종류가 고정된 문제 조건에서는 사실상 O(n)입니다. 추가 공간 복잡도는 O(n)입니다.

핵심 관찰

한 행동은 파이프 하나가 아니라 같은 종류의 파이프 전체를 여는 것입니다. 따라서 상태는 개별 간선의 개방 여부가 아니라 지금까지 선택한 종류의 순서와 감염 집합으로 충분합니다. 같은 종류를 다시 열어도 감염 집합이 변하지 않으므로 세 종류의 순열만 탐색합니다.

오답 접근과 반례

각 행동에서 새로 감염된 노드만 다음 BFS의 시작점으로 사용하면, 이전 행동으로 감염된 노드에서 새 종류의 파이프로 이어지는 경로를 놓칩니다. 예를 들어 A 파이프로 먼저 감염된 노드가 B 파이프의 입구라면, B를 열 때는 그 노드도 큐에 포함해야 합니다.

3. 문제 해결 코드 (Python)

from collections import deque


def solution(n, infection, edges, k):
    graph = [[] for _ in range(n)]

    for x, y, pipe_type in edges:
        x -= 1
        y -= 1
        graph[x].append((y, pipe_type))
        graph[y].append((x, pipe_type))

    def spread(infected, pipe_type):
        next_infected = infected.copy()
        queue = deque(infected)

        while queue:
            node = queue.popleft()

            for neighbor, edge_type in graph[node]:
                if edge_type == pipe_type and neighbor not in next_infected:
                    next_infected.add(neighbor)
                    queue.append(neighbor)

        return next_infected

    answer = 1

    def search(infected, used_types, actions):
        nonlocal answer
        answer = max(answer, len(infected))

        if actions == k or len(infected) == n:
            return

        for pipe_type in (1, 2, 3):
            if pipe_type in used_types:
                continue

            expanded = spread(infected, pipe_type)
            search(expanded, used_types | {pipe_type}, actions + 1)

    search({infection - 1}, set(), 0)
    return answer

구현 포인트

  • 양방향 트리이므로 각 간선을 양쪽 인접 리스트에 추가합니다.
  • BFS에서는 현재 열고 있는 파이프 타입과 같은 간선만 통과합니다.
  • 감염 상태는 다음 행동으로 이어지지만, DFS의 다른 분기와 공유하지 않도록 복사합니다.
  • 같은 파이프 타입을 다시 선택하지 않아 중복 탐색을 제거합니다.
  • k가 3보다 커도 종류가 3개뿐이므로 최대 3번의 유효한 행동만 진행됩니다.

4. 동일한 문제를 어떻게 풀었나 웹검색 하여 요약

공개된 풀이들은 모두 파이프 종류를 선택하는 순서와 감염 확산을 분리해 처리합니다.

  • 프로그래머스 공식 문제 페이지는 같은 종류의 파이프 전체를 한 번에 열고 닫는 행동과 최대 k번의 행동 조건을 설명합니다.
  • 10e01의 C++ 풀이는 세 종류의 간선 중 선택 순서를 DFS로 탐색하고, 각 순서에서 BFS로 감염을 확산하는 접근을 사용합니다.

연결 요소를 미리 계산하면 각 타입별 확산을 더 빠르게 처리할 수 있습니다. 이 글에서는 n ≤ 100, 파이프 타입 3개라는 제한을 활용해 구현이 직관적인 BFS를 매 단계 실행하는 방식을 선택했습니다.

마무리

이 문제는 트리 자체보다 “어떤 타입의 파이프를 어떤 순서로 열 것인가”가 핵심입니다. 가능한 순서는 매우 적으므로 DFS로 모두 시도하고, 한 타입을 열었을 때의 실제 감염 확산은 BFS로 계산하면 상태를 명확하게 분리할 수 있습니다.

#DFS#프로그래머스#난이도 4