boj 2606 :

문제 주소: https://www.acmicpc.net/problem/2606

난이도: silver 3

1.문제설명

• 네트워크 상에 컴퓨터들이 연결되어 있다.
• 이때 특정 컴퓨터에 바이러가 있다면
• 그 컴퓨터와 연결된 컴퓨터는 모두 바이러스에 걸린다
• 특정 컴퓨터에 바이러스가 있을 때 총 몇대를 감염시키나?

2.문제해결 아이디어.

• 연결관계를 인접리스트로 표현하자
• BFS를 이용해 특정 위치에서 방문한 곳을 visited에 기록한다.
• visited의 원소갯수 - 1이 결과이다(-1은 바이러스가 시작한 컴퓨터는 제외)

3.문제접근법

• bfs만 잘 구현하면된다. 아래가 핵심부분이다.

def bfs(start, graph, visited):
    queue = deque([start]) #deque를 사용할꺼고 시작은 start라는 파라미터에서 한다
    while queue: #deque에 원소가 있는동안
        v = queue.popleft() #맨 앞의 원소를 pop하고
        for node in graph[v]: # v에서 갈수있는 장소들 중에서
            if node not in visited: #visited에 없다면(가본적이 없다면)
                queue.append(node) #deque에 추가하고
                visited.add(node) #방문했다고 표시해준다.

4.특별히 참고할 사항

• 사실 -1을 안해서 오답이 났었다.
• 문제를 잘 읽자...

5.코드구현

from collections import deque
N = int(input())
K = int(input())
graph = [[] for i in range(N+1)]
for i in range(K):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

visited = set()

def bfs(start, graph, visited):
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for node in graph[v]:
            if node not in visited:
                queue.append(node)
                visited.add(node)

bfs(1, graph, visited)
print(len(visited) - 1)