백준 2606 바이러스

문제

바이러스

바이러스에 걸린 컴퓨터 개수를 구하자

난이도 : Silver3

---

풀이

1. 주어진 네트워크 쌍을 하나의 이중 리스트에 저장해 그래프 형태로 만들자.
2. visited를 만들어 전체 dfs가 종료됐을 때 vistied의 True 개수(방문한 노드 개수)를 찾자.

---

코드

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
data = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

graph = {i+1:[] for i in range(n)}
visited = [False for _ in range(n)]  # 방문 체크

for i in range(1, n+1):  # 그래프 형태로 만들어줌
    temp = []
    for d in data:
        if d[0] == i:
            graph[d[0]].append(d[1])
        elif d[1] == i:
            graph[d[1]].append(d[0])


def dfs(start):
    stack = [start]
    while stack:
        node = stack.pop()
        visited[node-1] = True
        for i in graph[node]:
            if not visited[i-1]:
                stack.append(i)

dfs(1)
print(visited.count(True) -1)  # 1번 컴퓨터가 True이므로 1을 빼줘야 함

        

---

결과