악곱 == 악성곱슬

BFS

---

해당 문제를 보고 BFS가 떠오른 이유는 다음과 같다.

1번 컴퓨터를 기준으로 연결된 컴퓨터에 바이러스가 전파된다는 것을 보고 주변 컴퓨터부터 하나씩 전파를 시키면 되겠다고 생각 → 가까운 것 먼저 → 너비우선 탐색(BFS)

사실 해당 문제는 BFS와 DFS모두 상관이 없다. 결국 전체 탐색을 해야 하는 문제이다. 최단경로를 구하는 유형의 문제가 아니기 때문에 둘 다 사용 가능하다.

해당 문제에서 입력으로 주어지는 형태는 2차원 배열의 형식이 아닌 두 점의 연결정보를 주었기 때문에 연결 리스트(Linked List)로 그래프에 대해 초기화 해주었다.

두 점의 연결 정보는 방향성이 없는 연결이기 떄문에 양방향 연결을 위해 (1, 2) 와 같은 입력이 주어진 경우 1번 노드의 연결리스트에 2를, 2번 노드의 연결리스트에 1을 각각 추가해줘야 한다. 그렇지 않으면 탐색 순서에 의해 오류가 발생할 수 있다.

import sys
from collections import deque

def bfs(start):
    queue = deque()
    queue.append(start)
    visited[start] = True
    while queue:
        vtx = queue.popleft()
        for v in linked_list[vtx]:
            # 이미 방문한 노드
            if visited[v] is True:
                continue
            # 방문 안한 노드
            queue.append(v)
            visited[v] = True

com = int(sys.stdin.readline().rstrip())
edge_cnt = int(sys.stdin.readline().rstrip())

# 인덱스가 1부터라 +1
linked_list = [[] for _ in range(com+1)]
for _ in range(edge_cnt):
    sv, ev = map(int, sys.stdin.readline().rstrip().split())
    # 단방향이 아니라 양방향 연결을 해주어야 작동한다
    linked_list[sv].append(ev)
    linked_list[ev].append(sv)
visited = [False]*(com+1)
visited[0] = True
bfs(1)
print(visited.count(True) - 2)