백준 / 바이러스 / 2606번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 바이러스 / 2606번 (실버 3단계)

문제 사이트: https://www.acmicpc.net/problem/2606

 

문제 설명

---

나의 풀이

from collections import deque

def bfs(graph, start, visited):
    q = deque([start])

    visited[start] = True

    while q:
        x = q.popleft()

        for i in range(len(graph[x])):
            y = graph[x][i]
            if not visited[y]:
                q.append(y)
                visited[y] = True
    
    # 자기 자신은 제외해야함
    return visited.count(True) - 1

N = int(input())
M = int(input())

graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)

for _ in range(M):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)

print(bfs(graph, 1, visited))

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/77

[Algorithm] 너비 우선 탐색(BFS, Breadth-First Search)