[알고리즘] 백준 2606 바이러스 - S3

• 문제링크

2024.08.23 풀이

import sys
input=sys.stdin.readline
from collections import deque

n=int(input())
m=int(input())
arr=[[] for _ in range(n+1)]
visited=[False]*(n+1)
for _ in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

queue=deque()
queue.append(1)
cnt=0
visited[1]=True
while queue:
    v=queue.popleft()
    for i in arr[v]:
        if visited[i]==False:
            visited[i]=True
            cnt+=1
            queue.append(i)

print(cnt)

다른 풀이

from collections import deque
n=int(input()) # 컴퓨터 개수
v=int(input()) # 연결선 개수
graph = [[] for i in range(n+1)] # 그래프 초기화
visited=[0]*(n+1) # 방문한 컴퓨터인지 표시
for i in range(v): # 그래프 생성
    a,b=map(int,input().split())
    graph[a]+=[b] # a에 b 연결
    graph[b]+=[a] # b에 a 연결 -> 양방향
visited[1]=1 # 1번 컴퓨터부터 시작이니 방문 표시
Q=deque([1])
while Q:
    c=Q.popleft()
    for nx in graph[c]:
        if visited[nx]==0:
            Q.append(nx)
            visited[nx]=1
print(sum(visited)-1)

• cnt로 갯수를 카운트하지 않고, visited를 0으로 초기화, 1로 변환 시키면서 visited의 합을 계산하는 방법
• 처음 시작점인 1인 경우를 제외해야하므로 -1 처리

check point

• cnt가 아닌 visited의 합 처리 방법 고려해보기

---

• ref