[백준 파이썬] # 2606 바이러스 (BFS 풀이)

Silver III

# 2606 바이러스 (BFS 풀이)

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

2606번: 바이러스

 

풀이 (BFS)

from collections import deque

n = int(input())
connect = int(input())
graph = [[] for i in range(n+1)]  #1
visited = [False]*(n+1)
cnt = 0

for i in range(connect):
    s, e = map(int, input().split())
    #2 네트워크 상 연결 : 양방향
    graph[s].append(e)
    graph[e].append(s)

def bfs(graph, v):
    global cnt
    queue = deque([v])  #3

    while queue:  #4
        pop = queue.popleft()  #5
        visited[pop] = True

        for i in graph[pop]:
            if visited[i]==False:
                visited[i] = True
                queue.append(i)  #6
                cnt += 1  #7
    print(cnt)

bfs(graph, 1)

 

풀이 설명

• graph 리스트의 index를 이용해서 n개의 컴퓨터가 각각 연결된 컴퓨터를 확인할 수 있도록 한다_#1
• 바이러스는 양방향으로 전파될 수 있으므로 두 방향에 대한 정보를 기입한다_#2
• BFS는 deque 안에 리스트를 사용한다_#3
• BFS는 큐 자료구조안에 모든 값이 없어질 때(queue == False) 까지 반복한다_#4
• 가장 먼저 기입된 요소를 pop 해주면서 체커 표시를 한다_#5
• 체커 표시된 컴퓨터의 리스트가 갖고 있는 요소(i)를 큐 구조에 append 해준다_#6
• 체커 표시가 되어 있지 않은(큐 안에 삽입된 적이 없는) i 값만을 사용해서 cnt를 증가시켜준다_#7

 

최대한 풀어서 설명하려 해보려고 노력했으나 쉽지 않다

DFS/BFS 풀이 중 어떤 문제는 visited 체커를 사용하는 반면 안하는 문제도 있는 것 같다.

그 차이에 대해 이해하려면 좀 더 많이 풀어봐야할 듯 하다

 

※ 미래의 내가 또 이해하지 못할 것 같아서 간단히 알고리즘을 그려보았다