백준 2606: 바이러스 (Python)

 

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

2606번: 바이러스

 

bfs 먼저 풀고 dfs 풀었다

 

# bfs

from collections import deque

n = int(input())
m = int(input())
com = [[] for _ in range(n+1)]

for i in range(m):
    data = input().split()
    com[int(data[0])].append(int(data[1]))
    com[int(data[1])].append(int(data[0]))

def bfs(v):
    count = 0
    visited = [False] * (n+1)
    queue = deque([v])
    visited[v] = True

    while queue:
        q = queue.popleft()
        visited[q] = True
        count += 1

        for i in com[q]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

    return count-1

print(bfs(1))

# dfs

n = int(input())
m = int(input())
com = [[] for _ in range(n+1)]

for i in range(m):
    d1, d2 = map(int, input().split())
    com[d1].append(d2)
    com[d2].append(d1)

visited = [0] * (n+1)

def dfs(v):
    visited[v] = 1

    for i in com[v]:
        if visited[i] == 0:
            dfs(i)

dfs(1)
print(sum(visited)-1)

 

bfs -> dfs 풀면서 코드가 좀더 간결해지고 시간이랑 메모리를 줄일 수 있는 방안으로 생각해보게 됨.

 

시행착오···