[python]2060_바이러스

사용한 자료구조 및 개념 : bfs, deque

 

💡 문제풀이 아이디어 및 어려웠던 점

💫 아이디어

1️⃣ bfs와 deque을 사용한다.

2️⃣ 노드를 queue에 추가하여 노드와 연결된 노드들을 순회한다.

3️⃣ next_v 노드가 감염되지 않았다면 감염시키고 next_v 노드의 연결된 노드들을 확인할 수 있게 queue에 추가한다.

4️⃣ queue가 빌 때까지 반복하여 감염된 컴퓨터 수를 확인한다.

 

---

 

Solution Code & 주석

import sys
from collections import deque

def bfs(v):
    result = 0
    infected[v] = True
    queue = deque([v])

    while queue:
        v = queue.popleft()
        for next_v in graph[v]:
            if not infected[next_v]:
                infected[next_v] = True
                result += 1
                queue.append(next_v)

    return result

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[] for _ in range(n + 1)]
infected = [False] * (n + 1)

for _ in range(m):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

print(bfs(1))

 

---

 

bfs를 활용하지 않은 재밌는 풀이

다른 사람의 풀이를 보던 중 재미있는 풀이법을 보았다.

1번 컴퓨터가 무조건 바이러스에 걸린다는 점과 set을 활용하여 푼 코드인데 시간도 훨씬 적게 걸리고 간단하고 신박하여 기록해놓는다!

import sys

input = sys.stdin.readline

a = int(input())
b = int(input())

b_lst = []

result = set()
for i in range(b) :
    num = list(map(int,input().split()))
    if 1 in num :
        result.add(num[0])
        result.add(num[1])
    else :
        b_lst.append(num)
    
while True :
    for i in b_lst :
        if i[0] in result :
            result.add(i[1])
            b_lst.remove(i)
            break
        elif i[1] in result :
            result.add(i[0])
            b_lst.remove(i)
            break
    else :
        break

print(len(result) - 1 )