바이러스 파이프 문제를 풀면서 실수한 부분 정리

1. 문제의 핵심 구조를 정확히 이해하지 못했다

이 문제에서 한 번의 행동은 다음 과정을 모두 포함한다.

특정 타입의 파이프를 연다
→ 해당 타입의 파이프를 통해 감염이 가능한 만큼 모두 퍼진다
→ 파이프를 다시 닫는다

처음에는 파이프의 열림, 닫힘을 별도의 상태로 생각해서 open 변수를 만들었다.

dfs(..., true);
dfs(..., false);

하지만 문제에서 말하는 행동 1회는 이미 열었다가 닫는 전체 과정이다.

따라서 DFS 한 단계 자체를 다음처럼 해석해야 한다.

현재 DFS 단계
= 타입 하나 선택
= 해당 타입 파이프 열기
= 감염 전파
= 해당 타입 파이프 닫기

그러므로 open === false라는 별도 분기는 필요하지 않다.

false 분기에서 cnt + 1을 하면, 실제로는 아무 파이프도 열지 않았는데 행동 횟수만 1회 사용한 것으로 처리되는 문제가 생긴다.

핵심은 ON/OFF를 무시하는 것이 아니라, DFS 한 단계 안에 ON → 전파 → OFF를 모두 포함하는 것이다.

2. 같은 타입의 파이프를 한 칸만 이동한다고 생각했다

처음에는 현재 감염된 배양체의 인접 노드만 검사했다.

let will_inf = [...infecs];

for (const inf of infecs) {
    for (const [node, type] of graph[inf]) {
        if (Type === type) {
            will_inf.push(node);
        }
    }
}

하지만 같은 타입의 파이프를 열어 둔 동안에는 새로 감염된 배양체에서도 계속 감염이 퍼진다.