[Baekjoon] 2606번 : 바이러스 (Python)

[Baekjoon] 2606번 : 바이러스 (Python)

 

목차

 

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

2606번: 바이러스

Python

 

방법 1 - 메모리 30840KB / 시간 68ms / 코드 길이 340B

 

DFS를 활용한 방법으로 1번을 시작으로 방문한 곳은 True가 될 수 있는 visit list를 구성한다.

이를 기반으로 합 - 1이 답이 되도록 구성한다.

import sys
input = sys.stdin.readline
n = int(input())
e = int(input())

l=[[] for _ in range(n+1)]

for i in range(e):
    a,b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)

visit = [False]*(n+1)

def dfs(v):
    visit[v] = True
    for i in l[v]:
        if not visit[i]:
            dfs(i)

dfs(1)
print(sum(visit)-1)

 

방법 2 - 메모리 30864KB / 시간 16ms / 코드 길이 B

 

BFS 기반으로 문제를 푸는 방법입니다.

collections의 deque 내장함수를 기반으로 문제를 풀었습니다.

 

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
e = int(input())

l=[[] for _ in range(n+1)]

for i in range(e):
    a,b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)

visit = [False]*(n+1)

def bfs(v):
    queue = deque([v])
    visit[v] = True

    while queue:
        t = queue.popleft()

        for i in l[t]:
            if not visit[i]:
                queue.append(i)
                visit[i] = True

bfs(1)
print(sum(visit)-1)