[정글 알고리즘] - [하] - 백준 2606 - 바이러스 실버3

이 문제의 핵심은 “그래프 전체의 성질”을 보는 것이 아니라, 1번 컴퓨터에서 시작했을 때 실제로 도달 가능한 컴퓨터가 몇 대인가를 구하는 것이다. 즉, 1번과 연결된 컴포넌트의 크기를 구한 뒤 자기 자신을 빼면 된다. [Source](https://www.acmicpc.net/problem/2606)

문제 요약

웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 감염되면, 그 컴퓨터와 네트워크 상에서 연결된 모든 컴퓨터도 감염된다. 여기서 1번 컴퓨터가 감염되었을 때, 최종적으로 몇 대의 컴퓨터가 추가로 감염되는지를 구하면 된다.

항목	내용
정점	컴퓨터
간선	네트워크 연결 정보
시작 노드	1번 컴퓨터
구해야 하는 값	1번에서 출발해 도달 가능한 모든 컴퓨터 수 - 1

문제를 한 줄로 바꾸면

이 문제는 결국 “1번 노드와 연결된 모든 정점 개수 구하기” 문제다. 단, 문제에서 묻는 것은 “1번 때문에 감염되는 다른 컴퓨터 수”이므로 마지막에는 1번 자신을 제외해야 한다.

왜 규칙으로 바로 못 풀까?

처음에는 정점 개수와 간선 개수만 보고 어떤 규칙으로 바로 답을 낼 수 있을 것처럼 보일 수 있다. 하지만 이 문제는 간선의 개수만으로는 절대 답을 알 수 없다.

경우 1

1 - 2 - 3 - 4

1번에서 시작하면 2, 3, 4가 감염된다.

정답: 3

경우 2

5 - 6
6 - 7

간선 수가 같아도 1번과 연결이 안 되어 있으면 감염은 퍼지지 않는다.

정답: 0

즉, 이 문제는 단순 계산이 아니라 1번에서 출발해 어디까지 갈 수 있는지 직접 따라가야만 알 수 있다.

그래프는 어떻게 저장할까?

이 문제는 컴퓨터 번호가 1번부터 N번까지 주어진다. 그래서 보통 인접 리스트를 다음처럼 만든다.

graph = [[] for _ in range(n + 1)]

여기서 n + 1 인 이유는 컴퓨터 번호를 인덱스로 그대로 쓰기 위해서다. 0번은 사용하지 않고, 1번부터 n번까지 쓰는 구조다.

의미

graph[1] → 1번과 연결된 컴퓨터들

graph[2] → 2번과 연결된 컴퓨터들

...

이 문제는 무방향 그래프다

문제의 연결 정보는 “서로 연결되어 있다”는 뜻이므로 방향이 없다. 즉, A와 B가 연결되어 있으면 A에서도 B로 갈 수 있고, B에서도 A로 갈 수 있다.

a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)

visited가 의미하는 것

이 문제에서 visited[i] = True 는 단순히 “한 번 본 적 있다”라는 뜻이 아니라, 1번에서 출발했을 때 i번 컴퓨터까지 도달 가능하다는 의미로 봐도 된다.

visited = [False] * (n + 1)

visited[1] = True

처음부터 1번을 True로 두는 이유는 탐색 출발점이 1번이기 때문이다. 그리고 DFS를 돌리면서 1번에서 갈 수 있는 컴퓨터들이 차례로 True로 바뀐다.

DFS 함수는 이렇게 생각하면 된다

현재 컴퓨터 node에 연결된 컴퓨터들을 하나씩 확인하면서, 아직 방문하지 않은 컴퓨터가 나오면 방문 처리 후 다시 DFS를 들어간다.

def dfs(node):
    for next_node in graph[node]:
        if not visited[next_node]:
            visited[next_node] = True
            dfs(next_node)

이 구조는 “현재 정점에서 연결된 미방문 정점들을 끝까지 타고 들어간다”는 DFS의 가장 기본 형태다.

왜 dfs(1)이 꼭 필요할까?

DFS 함수를 정의하는 것과 실행하는 것은 완전히 다르다. 함수를 만들어 두기만 하면 아무 탐색도 일어나지 않는다.

필수 시작점

dfs(1)

이 한 줄이 “1번 컴퓨터에서 감염을 시작하라”는 뜻이다. 만약 이 줄이 없으면 1번만 True인 상태로 끝나고, 정답은 항상 0처럼 나오게 된다.

정답을 왜 visited.count(True) - 1 로 구할까?

DFS가 끝나면 visited 안의 True들은 모두 “1번에서 감염 가능한 컴퓨터들”이다.

visited.count(True)

그런데 여기에는 출발점인 1번 컴퓨터도 포함되어 있다. 문제는 1번을 통해 추가로 감염되는 컴퓨터 수를 묻기 때문에, 자기 자신 1개를 빼야 한다.

print(visited.count(True) - 1)

헷갈리기 쉬운 포인트

실수 포인트	왜 틀리는가	정리
정점 수와 간선 수만 보고 규칙으로 풀려고 함	1번과 연결되어 있는지가 핵심이라 전체 개수만으로는 답이 안 나옴	반드시 1번에서 탐색해야 함
무방향 그래프인데 한쪽만 append 함	연결 정보를 절반만 저장하게 됨	양쪽 모두 추가
visited = True 처럼 전체를 바꿔버림	특정 노드가 아니라 리스트 자체를 덮어씀	visited[next_node] = True
dfs(1)을 호출하지 않음	탐색 함수만 정의되고 실제 탐색이 안 됨	반드시 dfs(1)
True 개수만 출력함	1번 컴퓨터까지 포함됨	-1 해줘야 함

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (n + 1)
visited[1] = True

def dfs(node):
    for next_node in graph[node]:
        if not visited[next_node]:
            visited[next_node] = True
            dfs(next_node)

dfs(1)

print(visited.count(True) - 1)

한 줄 요약

이 문제는 1번 컴퓨터에서 시작하는 DFS/BFS로 연결된 모든 컴퓨터를 방문하고, 방문 수에서 1을 뺀 값을 구하는 문제다.

마무리

이 문제는 그래프 문제의 가장 기본적인 형태다. 중요한 것은 “그래프 전체”가 아니라 1번에서 실제로 닿을 수 있는 범위만 보는 것이라는 점이다.

그래서 정답은 결국 1번이 포함된 연결 요소의 크기를 구한 뒤 자기 자신을 빼는 방식으로 나온다.

즉, 이 문제를 정확히 이해하는 핵심 문장은 이것이다. 1번과 연결된 모든 정점 수를 세고, 1번은 제외한다.