[CodeUp] 4503번 : 바이러스 (Python)

Python

방법 1 - 메모리 27724 / 시간 19 / 코드 길이 411B

바이러스에 감염되는 컴퓨터를 list를 통해 체크하도록 dfs 혹은 bfs를 작성하면 풀 수 있습니다.

본 방법은 dfs를 활용한 방법

n = int(input())
r = int(input())

t = [[] for _ in range(n)]

for i in range(r):
    a, b = list(map(int, input().split()))
    t[a - 1].append(b)
    t[b - 1].append(a)

vir = [0 for _ in range(n)]

def dfs(i):
    if i<0 or i>n-1:
        return 0

    if vir[i] == 1:
        return 0
    else:
        vir[i] = 1
        for k in t[i]:
            dfs(k-1)

dfs(0)
print(sum(vir)-1)

방법 2 - 메모리 30044 / 시간 20 / 코드 길이 524B

본 방법은 bfs를 활용한 방법

from collections import deque

n = int(input())
r = int(input())

t = [[] for _ in range(n+1)]
vir = [0 for _ in range(n+1)]

for i in range(r):
    a, b = list(map(int, input().split()))
    t[a].append(b)
    t[b].append(a)

def bfs(c, graph, visited):
    queue = deque([c])
    visited[c] = 1

    while queue:
        v = queue.popleft()

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = 1

bfs(1, t, vir)
print(sum(vir)-1)

0000