[백준] 2606. 바이러스 (Python)

이번에 풀어 볼 문제는 <백준 2606번. 바이러스>이다.

https://www.acmicpc.net/problem/2606

 

 

📌 문제 탐색하기

목표

• 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수 출력하기

해야 할 것

1. 컴퓨터의 네트워크 관계를 어떻게 저장할까?
2. 1번 컴퓨터와 연결되어 있는 컴퓨터를 어떻게 탐색할까?

입력

• 컴퓨터의 수 ( 1 이상, 100 이하 )
• 연결된 컴퓨터 쌍의 수 ( = 간선의 수 )
• 컴퓨터 1, 컴퓨터 2 형태로 간선이 주어짐

아이디어

• 컴퓨터의 네트워크 관계를 어떻게 저장할까?
  •  컴퓨터 == 정점, 컴퓨터 쌍 == 간선
  • 딕셔너리를 활용한 인접 리스트 ( 0번 인덱스에는 [] 저장하기 )
• 1번 컴퓨터와 연결되어 있는 컴퓨터를 어떻게 탐색할까?
  • DFS 또는 BFS로 탐색하기 ➡️ 나는 BFS 이용
  • BFS 탐색을 통해 도달할 수 있는 정점의 수 == 웜 바이러스에 걸리게 되는 컴퓨터의 수

📌 코드 설계하기

1. input 입력받고 그래프를 딕셔너리를 활용한 인접 리스트로 저장한다.

2. 1을 시작 정점으로 하여 BFS 탐색을 진행하고 방문한 정점의 집합 visited 반환한다.

3. len(visited)-1 를 출력한다. ➡️ " 1번 컴퓨터를 통해" 걸리게 되는 컴퓨터의 수이므로 1을 빼줘야 한다.

📌 정답 코드

import sys
from collections import deque

n = int(sys.stdin.readline()) #컴퓨터의 수
e = int(sys.stdin.readline()) # 간선의 수

graph = {i:[] for i in range(n+1)} #0~n까지

# 인접리스트 초기화
for _ in range(e):
    v1, v2 = map(int,sys.stdin.readline().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

def bfs(start, visited=[]):
    visited.append(start)
    queue = deque([start])
    while queue :
        cur_v = queue.popleft()
        for next_v in graph[cur_v]:
            if next_v not in visited:
                visited.append(next_v)
                queue.append(next_v)
    
    return visited

result = bfs(1)
print(len(result)-1)

📌 알게 된 것

• 문제 꼼꼼히 읽기 ! 1번 컴퓨터를 통해~ 인데 -1 안해주는 실수 같은거 하지말기..
• deque() 안에는 이터러블한 객체가 들어가야 함. 아니면 그냥 queue = deque() 로 빈 덱을 선언해줄 수는 있음.
  하지만, deque( 1 ) 처럼 int 값을 넣으면 오류 발생
• deque.pop() ➡️ 제일 오른쪽에서 빼기
• deque.popleft() ➡️ 제일 왼쪽에서 빼기