BOJ(백준) 2606번 바이러스 파이썬

 

2606번: 바이러스

---

코드

import sys
r = sys.stdin.readline
N = int(r()) # 노드 수
M = int(r()) # 간선 수

edge = [[] for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,r().split())
    edge[A].append(B)
    edge[B].append(A)

for e in edge:
    e.sort(reverse=True)

def virus():
    v = []
    stack = [1]
    visit = [False for _ in range(N+1)]
    while stack:
        node = stack.pop()
        if visit[node]:
            pass
        else:
            v.append(node)
            visit[node] = True
            stack += edge[node]
    return v

print(len(virus()) - 1)

 

해설

이전 문제인 DFS와 BFS [1260번]와 매우 유사하게 풀이하였다. 유일한 차이는 이 문제에서는 출력부분에서 DFS를 통한 연결된 시작점을 제외한 노드의 수를 출력하도록 했다는 점이다.

 

결과