[알고리즘][Python] 백준 2606 바이러스 문제 풀이

문제 출처 : www.acmicpc.net/problem/2606

2606번: 바이러스

---

문제 해석 : 1번 컴퓨터로 부터 바이러스가 퍼진다. 이때 네트워크상에 연결된 모든 컴퓨터가 감연되는데 이 수를 구하는 문제이다.

 

문제 풀이 : 다양한 방법으로 문제를 풀이할 수 있지만 자신의 부모를 찾는 연산을 통해서 부모 노드가 1인 모든 노드를 찾으면 되기 때문에 부모를 찾는 방법을 사용했다. 다만 입력의 순서 때문에 오류가 발생할 수 있기 때문에 2번의 union 연산을 진행했다.

 

가능한 다른 풀이 : DFS나 BFS로 문제를 풀이할 수 있다.

 

---

풀이 코드

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

    return parent[x]


def union(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())
arr = [list(map(int, input().split())) for _ in range(M)]

parent = [0] * (N+1)

for i in range(1, N+1):
    parent[i] = i

for i in range(2):
    for x,y in arr:
        union(parent,x,y)

answer = 0
for i in range(2,len(parent)):
    if parent[i] == 1:
        answer += 1
print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.