[백준_2606] 바이러스

풀이과정

1. 양방향 접근이 가능하다. 길에 해당하는 li리스트에 길을 추가할 때 양방향으로 추가한다.

li = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    li[a].append(b)
    li[b].append(a)

2. 진입 여부를 표시하는 check 리스트를 초기화하고, queue를 만든다. queue에는 첫 이동지점인 1을 추가한다.
   • check 리스트에서 진입한 곳은 1, 진입하지 않은 곳은 0이 되도록 한다.

check = [0]*(N+1)
que = deque()
que.append(1)

3. while문으로 BFS를 구현한다. 이때 진입한 곳을 0에서 1로 바꾼다.

while que:
    x = que.popleft()
    if not check[x]:
        check[x] = 1
        for i in li[x]:
            que.append(i)

4. 진입한 곳의 개수는 check의 요소들의 합에서 최초의 출발지점의 수(1개)를 뺀 값이다.
   • print(sum(check) - 1)

전체 코드

from collections import deque
N = int(input())
M = int(input())
li = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    li[a].append(b)
    li[b].append(a)

check = [0]*(N+1)

que = deque()
que.append(1)
while que:
    x = que.popleft()
    if not check[x]:
        check[x] = 1
        for i in li[x]:
            que.append(i)
print(sum(check) - 1)