[백준] 2606번 - 바이러스 (파이썬)

 

" 백준 2606번 바이러스 문제 파이썬 "

 

 

문제

 

 

 

" 💡 문제 해결 아이디어 "

 

바이러스 문제는 그래프에서 1에 연결되어 있는 노드를 탐색하여 그 갯수를 출력하는 문제이다.

방문한 노드는 visited 배열에 True로 저장하여 중복 탐색하지 않도록 구현한다.

 

예제 입력

주어지는 입력값을 이용하여 연결 관계 그래프를 생성하고 1번 노드를 시작으로 연결되어 있는 노드의 갯수를 카운트하면 정답을 도출할 수 있다.

 

연결 관계

예제 입력 값을 통하여 연결 관계 그래프를 생성하면 다음과 같은 그래프가 생성된다.

 

 

 

주의 사항!

 

입력받은 값들로 그래프를 그릴 때에 방향이 있는 그래프가 아니므로

node1에 node2을 연결해주었다면, node2에도 node1을 추가해주어야 한다.

 

 

만약 node1에 node2을 연결하는 작업만 진행한다면 아래와 같은 문제가 발생한다.

 

# 기존 입력값
2 1
2 3
5 1
5 2
5 6
4 7

# 예시 입력값
2 1
2 3
5 1
5 2
5 6
4 7

 

만약 예제 입력이 기존 입력값이 아닌 예시 입력값처럼 나온다면 1번 노드에는 어떠한 연결 관계도 형성되지 않기 때문에

start를 1로 주고 bfs 탐색을 수행하는 나의 코드의 경우에선 치명적인 오류로 작용한다.

 

 

코드

from collections import deque


def bfs(start, visited):
    queue = deque([start])
    cnt = 0
    visited[start] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if visited[i] == False:
                visited[i] = True
                queue.append(i)
                cnt += 1
    print(cnt)


n = int(input())  # 컴퓨터의 수
conn = int(input())  # 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수
visited = [False] * (n+1)  # 방문 체크

graph = [[] for _ in range(n+1)]  # 연결 관계 그래프
for i in range(1, conn+1):
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

bfs(1, visited)