[백준] 2606 - 바이러스

문제

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

웜 바이러스는 네트워크를 통해 전파되기 때문에 한 컴퓨터가 웜 바이러스에 걸리면 네트워크 상에서 연결된 모든 컴퓨터가 웜 바이러스에 걸린다.

예로 들어 그림 1과 같은 네트워크가 있다고 할 때, 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번, 5번 컴퓨터를 거쳐 3번, 6번 컴퓨터까지 전파된다. 즉, 2번, 3번, 5번, 6번 컴퓨터가 웜 바이러스에 걸리게 된다.

컴퓨터의 수와 네트워크 상에서 직접 연결되어 있는 컴퓨터의 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의의 수를 구하여라.

입력으로는 첫째 줄에 컴퓨터의 수가, 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이후로 한 줄 씩직접 연결되어 있는 컴퓨터 쌍이 주어진다.

 

 

풀이

이번 문제는 테이블 형식이 아니라 그래프 형식의 BFS 문제이다. 최소 경로를 구하는 문제가 아니기 때문에 DFS로 풀 수도 있을 것 같은데 아직 DFS에 대해 정리하지 않았기 때문에…… BFS로 풀어보겠다.

 

1. 입력값 초기화

컴퓨터의 수와 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수를 입력받는다.

cnt_computor = int(sys.stdin.readline())
cnt_pair = int(sys.stdin.readline())

 

2. 그래프 초기화

네트워크의 전체 연결 상태를 아는 상태에서 그래프 탐색을 수행하는 것이 좋을 것 같다.

def make_graph(cnt_computor: int, cnt_pair: int) -> dict:
    graph = {k: [] for k in range(1, cnt_computor + 1)}
    for _ in range(cnt_pair):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    return graph
    
    
graph = make_graph(cnt_computor, cnt_pair)

그래프 간선의 방향이 없으므로, 컴퓨터 연결 쌍을 입력받으면 두 정점 모두 연결되어 있는 점에 대한 정보를 업데이트해주어야 한다.

 

3. 너비 우선 탐색 구현

테이블 형식과 달리 visited를 정점을 key로 하고 방문 여부를 나타내는 bool 형식 값을 value로 하는 딕셔너리로 선언한다.

그리고 연결된 정점을 방문할 때도 방문 여부만 확인하면 된다.

def bfs(graph: dict, start: int = 1) -> dict:
    visited = {k: False for k in graph.keys()}
    
    # 시작점 방문
    queue = [start]
    visited[start] = True
    while queue:
        curr = queue.pop(0)
        # 연결된 정점 방문
        for i in graph[curr]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    return visited

 

3. 너비 우선 탐색 수행 및 결과값 출력

결과값을 출력할 때는 1번 컴퓨터 감염 여부를 제외해야 한다.

start = 1
infection = bfs(graph, start)
print(len([k for k, v in infection.items() if k != start and v]))

 

 

참고 문서

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