[python] 백준 - 2606 (바이러스)

2026.01.08ko 1 시리즈 · 알고리즘 #알고리즘

실버3 문제이며, 제한 시간은 1초이다.

문제

해결 과정

문제를 보면 1번 컴퓨터가 바이러스에 감염되며, 1번 컴퓨터를 통해 감염되는 컴퓨터의 개수를 구하는 문제이다. 따라서 집합으로 생각하면, 1이 포함된 집합의 원소의 개수가 몇 개인지 구하는 문제와 같다. 따라서 Union - Find 알고리즘을 이용해서 문제를 해결했다.

풀이

def find_parent(parent, x):
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x])
  return parent[x]

def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

n = int(input())
m = int(input())
parent = [x for x in range(n + 1)]
for _ in range(m):
  a, b = map(int, input().split())
  union_parent(parent, a, b)

for i in range(1, n + 1):
  find_parent(parent, i)

count = 0
for x in parent:
  if x == 1:
    count += 1

print(count - 1)

아직 서로소 집합 알고리즘을 많이 사용해보지 못했어서, 그래프 탐색으로 풀기보다 서로소 집합을 연습하고 싶어서 이 방식으로 풀어봤다.

아직 댓글이 없습니다.

문제

해결 과정

풀이

댓글

댓글 쓰기