[BOJ] 2626 바이러스

💡문제 분석 요약

• 한 컴퓨터가 웜에 걸리면 → 그 컴과 네트워크로 연결되어있는 모든 컴이 웜에 걸린다.
• 1번 컴을 통해 웜에 걸리는 컴퓨터 수를 출력해라.

엣지케이스

• 비어있거나 하나만 있는 케이스 : 입력이 비어있거나, 1개의 요소만 있는 경우

# 입력 
1 
1 
1 1

# 출력 
0

입출력

• 입력

7 # 컴퓨터 수 N
6 # 컴퓨터 쌍 수 (간선 수) M
1 2 # 간선 수 만큼 연결된 컴퓨터 번호쌍이 주어진다.
2 3
1 5
5 2
5 6
4 7

• 출력

4 # 1번 컴을 통해 웜에 걸리는 컴퓨터 수

1 ≤ 컴퓨터 수 N ≤ 100

1 ≤ 간선 수 M ≤ 양수

시간제한 : 1초

💡알고리즘 설계 (수도 코드)

1. 입력값 받기
   1. n
   2. m
   3. com = {i:[] for i in range(1,n+1)}
   4. visited = [0]*(n+1)
   5. 번호 쌍 받아서 인접 리스트에 저장
2. 1번 컴퓨터를 시작으로 탐색 시작해서 연결된 컴퓨터 개수 세기
   1. #0. 큐 만들고 체크인
   2. #1. while 큐에서 하나 뽑기
   3. #2. 목적지인가?
   4. #3. 갈 수 있는 곳 순회
   5. #4. 갈 수 있나?
   6. #5. 체크인
   7. #6. 큐에 넣

💡코드

34044 KB 64 ms

import sys
from collections import deque

def bfs(node,com,visited):
    num_com = 0
    #0. 큐 만들고 체크인
    q = deque([node])
    visited[node] = True

    while q:
        #1. 큐에서 하나 뽑기
        v = q.popleft()

        #2. 목적지인가
        
        #3. 갈 수 있는 곳 순회
        for item in com[v]:
            #4. 갈 수 있나?
            if not visited[item]:
                #5. 체크인
                visited[item] = True
                num_com += 1
                #6. 큐에 넣기
                q.append(item)

    return num_com
def solution():
    n = int(sys.stdin.readline().strip())
    m = int(sys.stdin.readline().strip())
    com = {i:[] for i in range(1,n+1)}
    visited = [False]*(n+1)
    for _ in range(m):
        u,v = map(int, sys.stdin.readline().strip().split())
        com[u].append(v)
        com[v].append(u)
    
    wom_num = bfs(1,com,visited)
    
    return wom_num

if __name__=="__main__":
    print(solution())

💡시간복잡도

O(N+M)

💡 느낀점 or 기억할정보

• 인접 리스트 & bfs 구현시 갈 수 있는 곳 순회하는 코드

        #3. 갈 수 있는 곳 순회
        for item in com[v]:
            #4. 갈 수 있나?
            if not visited[item]:
                #5. 체크인
                visited[item] = True
                num_com += 1
                #6. 큐에 넣기
                q.append(item)