프로그래머스

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

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

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

파이프 종류별 선택 순서를 DFS로 탐색하고 감염 확산을 BFS로 처리해야 하지만, 파이프 종류가 3개로 고정되어 유효한 순서가 최대 16개로 제한된다. 상태 복사와 두 탐색의 결합은 필요하지만 탐색 공간과 입력 제한이 작으므로 Level 3으로 재평가했다.

1. 문제 요약

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

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

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

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

그래프 구조와 방문 기록

각 행동에서 선택할 수 있는 파이프 종류는 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를 열 때는 그 노드도 큐에 포함해야 한다.

감염 집합 불변식

DFS의 각 호출에서 infected는 지금까지 선택한 파이프 종류들을 순서대로 연 뒤 감염되어 있는 배양체의 집합이다. 한 종류를 추가하면 BFS는 이 집합의 모든 원소를 동시에 시작점으로 삼아 해당 타입의 연결 요소를 끝까지 확장하므로, 행동이 끝난 뒤에는 기존 감염이 사라지지 않고 새로 도달 가능한 노드만 더해진다. set.copy()를 통해 분기마다 이 집합을 독립적으로 만들기 때문에 한 순서의 감염 결과가 다른 순서의 탐색을 오염시키지 않는다.

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번의 유효한 행동만 진행된다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 감염 시작점 하나와 한 번의 파이프 확산을 확인할 수 있다.

assert solution(1, 1, [], 0) == 1
assert solution(2, 1, [[1, 2, 1]], 1) == 2

4. 참고 풀이 비교

  • 10e01의 C++ 풀이는 세 종류의 간선 중 선택 순서를 DFS로 탐색하고, 각 순서에서 BFS로 감염을 확산하는 접근을 사용한다.

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

마무리

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

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