백준 2606 바이러스 (Python)

Problem

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

Solution

import sys

N = int(sys.stdin.readline())
num = int(sys.stdin.readline())

network = {i+1: [] for i in range(N)}
for _ in range(num):
    a, b = list(map(int, sys.stdin.readline().split()))
    network[a].append(b)
    network[b].append(a)

computers = [i+1 for i in range(N)]

def dfs(com):
    # end
    if com not in computers:
        return

    # visited
    if com in computers:
        computers.remove(com)

    # next
    connected = network[com]
    for com in connected:
        dfs(com)

dfs(1)
print(N - len(computers) -1)

DFS를 이용하여 1번 컴퓨터와 연결되어 있는 컴퓨터들을 지웠다. computers에 남아있는 컴퓨터들은 1번 컴퓨터와 연결되지 않은 컴퓨터로 바이러스에 감염되지 않는다.

Reference