[알고리즘][백준][파이썬] 바이러스 2606번

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

4

---

풀이1 - DFS

정답코드 - DFS 

n = int(input())
m = int(input())
graph = [[]*n for _ in range(n+1)]# 2차원 리스트를 초기화
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b) # a에 b 연결
    graph[b].append(a) # b에 a 연결 (양방향)
    
cnt = 0
visited = [0]*(n+1) # 방문한 컴퓨터인지 표시

def dfs(start):
    global cnt

    visited[start] = 1
    for i in graph[start]:
        if visited[i]==0:
            dfs(i)
            cnt +=1
            
dfs(1)

• 경로를 저장하기 위한 2차원 리스트 생성
• 총 m개의 간선을 입력받아 경로를 변수graph에 저장
• 다녀간 정점을 확인하기 위한 변수 생성
• 들리지않은 정점이면 dfs()를 이용하여 다시 반복

 

분석 

1. 데이터 입력처리

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

graph = [[]*n for _ in range(n+1)]# 2차원 리스트를 초기화

for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b) # a에 b 연결
    graph[b].append(a) # b에 a 연결 (양방향)

• graph[1]에는 1과 연결된 컴퓨터가 저장된다. (양방향도 고려)
• ex) 컴퓨터 1과 연결된 2, 5 컴퓨터

 

2. DFS 탐색

cnt = 0
visited = [0]*(n+1) # 방문한 컴퓨터인지 표시

def dfs(start):
    global cnt

    visited[start] = 1
    for i in graph[start]:
        if visited[i]==0:
            dfs(i)
            cnt +=1

---

풀이2 - BFS

from collections import deque
n=int(input()) # 컴퓨터 개수
v=int(input()) # 연결선 개수
graph = [[] for i in range(n+1)] # 그래프 초기화
visited=[0]*(n+1) # 방문한 컴퓨터인지 표시
for i in range(v): # 그래프 생성
    a,b=map(int,input().split())
    graph[a]+=[b] # a에 b 연결
    graph[b]+=[a] # b에 a 연결 -> 양방향
visited[1]=1 # 1번 컴퓨터부터 시작이니 방문 표시

def bfs(x):
    Q=deque([x])
    while Q:
        c=Q.popleft()
        for nx in graph[c]:
            if visited[nx]==0:
                Q.append(nx)
                visited[nx]=1
    return visited
bfs(1)
print(sum(visited)-1)