[Python] 2606 - 바이러스

문제

2606번: 바이러스

문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다.

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

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

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

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

입력

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

출력

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

---

풀이

• 같은 네트워크에 있으면 감염되는 방식이니 1과 연결된 네트워크를 찾는 문제로 완전탐색을 통해서 풀 수 있다.

• BFS나 DFS 어느 것을 사용해도 풀 수 있고 여기서는 BFS를 사용해서 풀었다.

• 연결된다는 의미가 방향성을 가지고 있지 않아서 무방향 그래프를 구현하기 위해 dict자료형을 사용했고 한번 연결값이 주어지면 양방향에서 모두 값을 추가해 구현했다.

• 단순히 숫자 값만 가지고 큐를 구성하면 돼서 collections에 deque를 사용해 큐를 구현했다.

설명

• 네트워크의 연결이 주어지면 네트워크에 해당 값이 있는지 확인하고
  • 없으면 배열에 넣어서 추가
  • 있으면 배열 뒤에 append로 추가

  했다.

• 1과 연결된 네트워크를 찾으면 되므로 1을 첫 인자로 주고 큐에 담아서 BFS 탐색을 시작한다.

• BFS
  1. 큐에서 하나를 뽑아 방문한 컴퓨터인지 혹은 다음 방문할 컴퓨터가 있는지 확인한다.
  2. 방문하지 않았다면 방문했다는 표시를 해주고 다음으로 방문할 컴퓨터를 찾는다.
  3. 다음으로 방문할 컴퓨터가 큐에 있는지 확인하고 없으면 추가한다.
  4. 추가했으면 해당 컴퓨터를 방문했으니 횟수를 1증가시켜준다.

답

from sys import stdin
from collections import deque

input = stdin.readline


def virus(n, N):
    visited = [False for _ in range(N + 1)]
    que = deque([1])
    cnt = -1
    # bfs
    while que:
        cur = que.popleft()
        # 다음으로 갈 곳이 없거나 방문한 노드면 넘어감
        if cur not in network or visited[cur]:
            continue
        # 방문 표시
        visited[cur] = True
        # 다음 방문 노드 추가
        for _next in n[cur]:
            # 이미 방문했거나 이미 큐에 있으면 넘어감
            if visited[_next] or _next in que:
                continue
            que.append(_next)
        cnt += 1
    return cnt


if __name__ == "__main__":
    N = int(input())
    T = int(input())
    network = dict()
    for _ in range(T):
        n1, n2 = map(int, input().split())
        if n1 not in network:
            network[n1] = [n2]
        else:
            network[n1].append(n2)
        if n2 not in network:
            network[n2] = [n1]
        else:
            network[n2].append(n1)
    res = virus(network, N)
    print(res)

더 좋은 풀이

• deque를 통해 큐를 구현할때 나는 배열을 사용해서 큐에 있는지 확인하는 조건이 필요했다.

  ⇒ 배열이 아니라 set을 사용해서 중복이 없게 추가한다면 해당 조건이 없어도 된다.

• 방문을 확인하는 로직을 미리 배열을 만들어 인덱로 찾아가게끔 만들었다.

  ⇒ 방문했을때마다 visited배열에 추가하면 인덱스도 필요하지 않고 방문횟수도 visited배열을 통해 한번에 확인할 수 있다.

Uploaded by Notion2Tistory v1.1.0