BOJ 2606: 바이러스

Note

BFS(너비 우선 탐색)를 활용하여 연결된 컴포넌트를 찾는 문제입니다.

---

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

문제 링크: https://www.acmicpc.net/problem/2606

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제

예제 입력 1:

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

예제 출력 1:

4

---

문제 분석

이 문제는 연결된 컴포넌트를 찾는 문제입니다. 1번 컴퓨터에서 시작하여 네트워크로 연결된 모든 컴퓨터를 찾아야 합니다.

그래프 표현

인접 리스트 (Adjacency List) 방식으로 그래프를 표현합니다:

• 각 컴퓨터에 연결된 컴퓨터들의 리스트를 저장
• 양방향 네트워크이므로 양쪽 모두에 간선을 추가

예제 입력 1의 그래프:

1: [2, 5]
2: [1, 3, 5]
3: [2]
4: [7]
5: [1, 2, 6]
6: [5]
7: [4]

핵심 포인트

1. 1번 컴퓨터에서 시작: BFS나 DFS로 1번과 연결된 모든 컴퓨터 탐색
2. 1번 컴퓨터 제외: 결과에서 1번 컴퓨터는 제외하고 카운트
3. 양방향 그래프: 네트워크는 양방향이므로 양쪽 모두에 간선 추가

---

해결 방법

BFS를 사용하여 1번 컴퓨터에서 시작하여 연결된 모든 컴퓨터를 탐색합니다:

1. 인접 리스트로 그래프 구성
2. BFS로 1번 컴퓨터에서 시작하여 연결된 모든 컴퓨터 탐색
3. 방문한 컴퓨터의 개수를 세되, 1번 컴퓨터는 제외

---

코드 구현

제공된 코드

import sys
from collections import deque
 
readline = sys.stdin.readline
 
computer_count = int(readline().rstrip())
 
computers = [False] * (computer_count + 1)
 
network_count = int(readline().rstrip())
 
graph: list[list[int]] = [[] for _ in range(computer_count + 1)]
 
# graph 구하기
for _ in range(network_count):
    start, end = map(int, readline().rstrip().split())
 
    graph[start].append(end)
    graph[end].append(start)
 
queue = deque()
 
queue.append(1)
computers[1] = True
 
while queue:
    pc = queue.popleft()
    for i in graph[pc]:
        if not computers[i]:
            computers[i] = True
            queue.append(i)
 
result = 0
for i in range(2, computer_count + 1):
    if computers[i] == True:
        result += 1
 
print(result)

코드 분석

1. 입력 처리

import sys
from collections import deque
 
readline = sys.stdin.readline
 
computer_count = int(readline().rstrip())
network_count = int(readline().rstrip())

• 입력 최적화를 위해 sys.stdin.readline() 사용
• 컴퓨터의 수와 네트워크 연결 수를 입력받음

2. 그래프 초기화

computers = [False] * (computer_count + 1)
graph: list[list[int]] = [[] for _ in range(computer_count + 1)]

• computers: 방문 여부를 저장하는 배열
• graph: 인접 리스트로 그래프 표현

3. 그래프 구성

for _ in range(network_count):
    start, end = map(int, readline().rstrip().split())
    graph[start].append(end)
    graph[end].append(start)

• 양방향 네트워크이므로 양쪽 모두에 간선 추가
• 예: 1 2 입력 시 graph[1]에 2 추가, graph[2]에 1 추가

4. BFS 탐색

queue = deque()
queue.append(1)
computers[1] = True
 
while queue:
    pc = queue.popleft()
    for i in graph[pc]:
        if not computers[i]:
            computers[i] = True
            queue.append(i)

자세한 설명은 BFS 알고리즘 포스트를 참고하세요.

5. 결과 계산

result = 0
for i in range(2, computer_count + 1):
    if computers[i] == True:
        result += 1
 
print(result)

• 2번부터 마지막 컴퓨터까지 순회 (1번 제외)
• 방문한 컴퓨터의 개수를 세어 출력

개선된 코드

더 Pythonic하게 작성한다면:

import sys
from collections import deque
 
readline = sys.stdin.readline
 
n = int(readline().rstrip())
m = int(readline().rstrip())
 
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
 
# 그래프 구성
for _ in range(m):
    a, b = map(int, readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)
 
# BFS 탐색
queue = deque([1])
visited[1] = True
count = 0
 
while queue:
    v = queue.popleft()
    
    for neighbor in graph[v]:
        if not visited[neighbor]:
            visited[neighbor] = True
            queue.append(neighbor)
            count += 1  # 1번 제외하고 카운트
 
print(count)

개선 사항:

• 변수명을 더 명확하게
• BFS 탐색 중에 바로 카운트하여 마지막 순회 불필요
• computers[i] == True → not visited[i] (더 Pythonic)

---

시간 및 공간 복잡도

시간 복잡도

• 그래프 구성: O(M) - 네트워크 연결 수만큼
• BFS 탐색: O(N + M) - 모든 컴퓨터와 연결을 한 번씩 방문
• 전체: O(N + M)

공간 복잡도

• 그래프 저장: O(N + M) - 인접 리스트
• 방문 배열: O(N)
• BFS 큐: O(N) - 최악의 경우
• 전체: O(N + M)

---

예제 동작 과정

예제 입력 1: n=7, m=6

그래프 구성:

1: [2, 5]
2: [1, 3, 5]
3: [2]
4: [7]
5: [1, 2, 6]
6: [5]
7: [4]

BFS 탐색 (시작: 1):

큐: [1]
1 처리 → 방문 표시, 연결된 [2, 5]를 큐에 추가, count = 2
큐: [2, 5]
2 처리 → 연결된 [3]을 큐에 추가 (1, 5는 이미 방문), count = 3
큐: [5, 3]
5 처리 → 연결된 [6]을 큐에 추가 (1, 2는 이미 방문), count = 4
큐: [3, 6]
3 처리 → 연결된 정점 모두 방문함
큐: [6]
6 처리 → 연결된 정점 모두 방문함
큐: []

결과: 4 (2, 3, 5, 6번 컴퓨터)

참고: 4번과 7번 컴퓨터는 1번과 연결되어 있지 않으므로 감염되지 않습니다.

---

DFS로도 해결 가능

이 문제는 DFS로도 해결할 수 있습니다:

import sys
 
readline = sys.stdin.readline
 
def dfs(graph, v, visited):
    visited[v] = True
    count = 1 if v != 1 else 0  # 1번 제외
    
    for neighbor in graph[v]:
        if not visited[neighbor]:
            count += dfs(graph, neighbor, visited)
    
    return count
 
n = int(readline().rstrip())
m = int(readline().rstrip())
 
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
 
for _ in range(m):
    a, b = map(int, readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)
 
print(dfs(graph, 1, visited))

---

관련 알고리즘

• BFS (너비 우선 탐색)
• DFS (깊이 우선 탐색)
• 연결된 컴포넌트 찾기
• Python 입력 최적화