BOJ(백준) 2606[바이러스]

이번 글에서는 백준 2606번 문제 "바이러스"를 함께 해결해 보겠습니다. 이 문제는 네트워크 상에서 컴퓨터 바이러스가 퍼지는 것을 시뮬레이션하여 감염된 컴퓨터의 수를 계산하는 문제입니다.

1. 문제 설명

1) 문제 개요

•  한 컴퓨터가 바이러스에 감염되면 네트워크를 통해 연결된 모든 컴퓨터로 바이러스가 퍼집니다.

•  1번 컴퓨터가 바이러스에 감염되었을 때, 네트워크를 통해 바이러스에 감염되는 컴퓨터의 수를 계산하는 문제입니다.

2) 입력

•  첫 줄에 컴퓨터의 수 N (1 ≤ N ≤ 100)과 연결된 쌍의 수 T가 주어집니다.

•  다음 줄부터 T개의 줄에 걸쳐 각 줄에 두 정수 a와 b가 주어집니다. 이는 a번 컴퓨터와 b번 컴퓨터가 연결되어 있다는 의미입니다.

3) 출력

•  1번 컴퓨터를 통해 바이러스에 감염되는 컴퓨터의 수를 출력합니다.

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 컴퓨터의 수 N과 연결된 쌍의 수 T를 입력받습니다.

2) 그래프 구성

• 인접 리스트를 사용하여 각 컴퓨터 간의 연결 상태를 저장합니다.

• 컴퓨터의 번호는 1부터 시작하므로 인덱스 조정 없이 그대로 사용합니다.

3) BFS를 이용한 감염 시뮬레이션

• BFS(너비 우선 탐색)를 사용하여 1번 컴퓨터로부터 바이러스가 퍼지는 과정을 시뮬레이션합니다.

• 큐를 사용하여 방문할 컴퓨터를 추적하고, 방문한 컴퓨터를 기록하여 중복 방문을 방지합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# 컴퓨터(노드)의 수를 입력받음
N = int(input())
# 그래프를 저장할 인접 리스트를 초기화 (1번 인덱스부터 사용하기 위해 N+1)
adj = [[] for _ in range(N+1)]

# 연결된 컴퓨터 쌍의 수를 입력받음
T = int(input())
# 각 연결 정보를 입력받아 인접 리스트에 추가
for _ in range(T):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

# 각 컴퓨터의 방문 여부를 저장할 리스트를 초기화 (처음엔 모두 방문하지 않음)
visited = [0] * (N+1)

# BFS를 위한 큐를 초기화하고, 1번 컴퓨터(감염된 컴퓨터)를 큐에 추가
q = []
q.append(1)
visited[1] = 1  # 1번 컴퓨터를 방문 처리
ans = 0         # 감염된 컴퓨터 수를 세기 위한 변수

# 큐가 빌 때까지 반복
while q:
    s = q.pop(0)            # 큐의 앞에서부터 노드를 꺼냄
    for i in adj[s]:        # 꺼낸 노드와 연결된 모든 노드를 확인
        if visited[i] == 0: # 만약 해당 노드를 아직 방문하지 않았다면
            q.append(i)     # 큐에 추가하고
            visited[i] = 1  # 방문 처리
            ans += 1        # 감염된 컴퓨터 수 증가

# 감염된 컴퓨터 수를 출력
print(ans)

 

4. 코드 설명

1) 입력 받기

• N과 T를 입력받고, 각 컴퓨터의 연결 상태를 인접 리스트에 저장합니다.

 

2) 그래프 구성

• 인접 리스트 adj를 사용하여 각 컴퓨터의 연결 상태를 저장합니다.

 

3) BFS를 이용한 감염 시뮬레이션

• 큐 q를 사용하여 BFS를 구현합니다.

• 1번 컴퓨터를 시작으로 감염된 컴퓨터를 큐에 추가하고, 방문한 컴퓨터는 visited 리스트에 표시합니다.

• 큐가 빌 때까지 연결된 모든 컴퓨터를 탐색하여 감염된 컴퓨터의 수를 계산합니다.

 

4) 결과 출력

• 최종적으로 감염된 컴퓨터의 수를 출력합니다.

 

***

1. 그래프 구성

예를 들어, 컴퓨터의 연결 정보가 다음과 같다고 해보겠습니다

 

1 - 2

1 - 5

2 - 3

2 - 4

이를 인접 리스트로 표현하면

adj = [

    [],

    [2, 5],  # 1번 컴퓨터와 연결된 컴퓨터들

    [1, 3, 4],  # 2번 컴퓨터와 연결된 컴퓨터들

    [2],  # 3번 컴퓨터와 연결된 컴퓨터들

    [2],  # 4번 컴퓨터와 연결된 컴퓨터들

    [1]  # 5번 컴퓨터와 연결된 컴퓨터들

]

 

2. BFS 시뮬레이션 과정

• 초기 상태: q = [1], visited = [0, 1, 0, 0, 0, 0], ans = 0

• 1번 컴퓨터 처리: q = [], visited = [0, 1, 1, 0, 0, 1], ans = 2 (2번과 5번이 큐에 추가됨)

• 2번 컴퓨터 처리: q = [5], visited = [0, 1, 1, 1, 1, 1], ans = 4 (3번과 4번이 큐에 추가됨)

• 5번 컴퓨터 처리: q = [3, 4], visited = [0, 1, 1, 1, 1, 1], ans = 4 (더 이상 방문할 노드 없음)

• 3번 컴퓨터 처리: q = [4], visited = [0, 1, 1, 1, 1, 1], ans = 4 (더 이상 방문할 노드 없음)

• 4번 컴퓨터 처리: q = [], visited = [0, 1, 1, 1, 1, 1], ans = 4 (더 이상 방문할 노드 없음)

최종적으로 감염된 컴퓨터의 수는 4입니다.

 

***

5. Github으로 확인

coTest/BOJ/BOJ01_07_01_2606.py at main · pcy4196/coTest