2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어

www.acmicpc.net

tip

그래프 탐색 문제에 앞서 bfs와 dfs를 언제 써야하는지에 대한 팁을 적어보겠습니다

bfs문제는 최단경로 탐색할떄 유용 (시작정점에서 주어진 정점까지 최단경로 찾기, 방문하지 않는 노드가 있어도 될때, 일부 경로만 탐색하는 경우, 미로찾기 문제)
dfs는 전체중 일부경로만 정답인 경우 (성공적인 결론을 내릴 때까지 트리 탐색, 모든 경우를 방문해야하는 경우, 모든 경우를 구한 후 일부만선택(완탐))

문제 풀이

바이러스 문제는 일부 경로만 탐색하는 경우라 생각했기 때문에 bfs풀이방법을 택했습니다
bfs를 풀 때 항상 주시할건 큐를 만들어 큐 리스트가 빌때까지 무언가를 반복하는 것

# 가까운 연결되어있는 것들 찾는 문제 = bfs
from collections import deque 

def bfs(computers, v, visited):
    queue = deque([v])
    visited[v] = 1
    while queue:
        for i in computers[queue.popleft()]:
            if visited[i] == 0:
                visited[i] = 1
                queue.append(i)
                
n = int(input())
line = int(input())
computers = [[] for _ in range(n+1)]
visited = [0] * (n+1)

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

# print(computers)
bfs(computers, 1, visited)
print(sum(visited) - 1)

[백준 2606] (bfs)바이러스 - python

tip

문제 풀이

티스토리툴바