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

1. 생각정리

• 문제를 좀 풀다 보니까 대충 감은 오는 것 같다
• 연결 정보는 이차원 리스트에 (1행에 1과 연결된 요소들 다 넣기, 2행에 2와 연결된 요소들 다 넣기...)의 느낌으로 입력받고, n+1 크기의 일차원 리스트를 통해 바이러스에 걸리는 것을 확인했는지 여부를 체크해준다
• 컴퓨터의 수가 적으므로, DFS로 모든 연결정보를 탐색하고, visited정보를 바꿀 때마다 결괏값+=1 해주어 최종 바이러스 걸린 컴퓨터 개수를 도출한다

 

2. 코드 구현

from collections import deque
#컴퓨터의 수 1<=n<=100
n = int(input())
#연결 수
m = int(input())
#m만큼 연결 정보
mapp = [[] for _ in range(n+1)]
visited = [False]*(n+1)
for _ in range(m):
    x,y = map(int, input().split())
    mapp[x].append(y)
    mapp[y].append(x)

for i in mapp:
    i.sort()
    
def bfs():
    result = 0
    q=deque([1])
    while q:        
        temp = q.popleft()
        if not visited[temp]:
            visited[temp] = True
            result+=1
            for i in mapp[temp]:
                if not visited[i]:
                    q.append(i)                    
    print(result-1)    
bfs()