algorithm

[백준/python] 2606 - 바이러스

현재의 현제 2022. 9. 28. 21:42

 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어

www.acmicpc.net

| DFS 풀이

bilgisayar = int(input())
n = int(input())
graph = [[] for _ in range(bilgisayar + 1)]
check = [0] * (bilgisayar + 1)
cnt = 0

for _ in range(n):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(i):
    global cnt
    check[i] = 1
    cnt += 1
    for v in graph[i]:
        if check[v] == 0:
            check[v] = 1
            dfs(v)

for i in graph[1]:
    if check[i] == 0:
        dfs(i)

print(cnt - 1)

| 알고리즘

지극히 평범한 연결요소 개수 문제 bfs로도 풀어봐야겠다. 점점 dfs bfs와 친해지고 있는 너낌

 

| BFS 풀이

from collections import deque

bilgisayar = int(input())
n = int(input())
graph = [[] for _ in range(bilgisayar + 1)]
check = [0] * (bilgisayar + 1)
cnt = 0

for _ in range(n):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def bfs(i):
    global cnt
    que = deque(graph[i])
    check[i] = 1
    while que:
        target = que.popleft()
        check[target] = 1
        for v in graph[target]:
            if check[v] != 1:
                check[v] = 1
                que.append(v)
for i in graph[1]:
    if check[i] == 0:
        bfs(i)

print(sum(check) - 1)