백준 2606 바이러스 (DFS)

이번에는 저번에 공부한 것을 토대로 DFS를 구현하는 문제이다. 오히려 저번 문제보다 쉬운게 함정이다.

1번 컴퓨터가 감염될때 감염되는 컴퓨터의 수는 4이다. 따라서 숫자만 구해주면 된다.

DFS로 풀게되면 1->2->3->5->6순으로 가게 된다. 그런데 우리는 순서는 중요하지 않아서 stack에 넣어줄때 그냥 때려 넣기만 하면 된다.

따라서 1260 문제 (guccin.tistory.com/87)보다 쉽게 코딩이 가능하다.

 

n = int(input())
m = int(input())
graph = {}
for i in range(m):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = [b]
    else:
        graph[a].append(b)
    if b not in graph:
        graph[b] = [a]
    else:
        graph[b].append(a)
# DFS
stack = [1]
out = []
while stack:
    t = stack.pop()
    if t not in out:
        out.append(t)
        if t in graph:
            tmp = list(set(graph[t]) - set(out))
            stack += tmp
print(len(out)-1)

 

이제 BFS로 풀어본다. 이때 queue는 deque를 선언하여 좀더 빠른게 큐를 사용한다.

n = int(input())
m = int(input())

graph = []
from collections import deque
visited = [0 for i in range(m)]
for _ in range(m):
    tmp = list(map(int, input().split()))
    graph.append(tmp)

# 1부터 실행한다.
queue = deque([1])
infection = []
while len(queue) != 0:
    target = queue.popleft()
    infection.append(target)#감염된거 넣어줌(1포함)
    tmp = []
    for i in range(len(visited)):
        if visited[i] == 0: #안들른경우
            if graph[i][0] == target:
                tmp.append(graph[i][1])
                visited[i] = 1
            elif graph[i][1] == target:
                tmp.append(graph[i][0])
                visited[i] = 1
    #tmp가 queue에 속하지 않고 infection에 속하지 않으면
    for i in tmp:
        if i not in queue:
            queue.append(i)
print(len(infection)-1)

아쉬운점은 코드의 길이가 늘어나고 시간이 오래걸렸다. 이유는 처음에 그래프의 연결을 전처리 하지 않기도 했고, 이후에 매번 m만큼의 반복을 돌기 때문인거 같다.