백준 2606 문제 풀이 python

🐒 바이러스

https://www.acmicpc.net/problem/2606

✍ 나의 풀이

import sys


n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
infected = [False] * (n+1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(x):
    infected[x] = True
    for i in graph[x]:
        if not infected[i]:
            dfs(i)

dfs(1)

print(infected.count(True)-1)

15분 가량 걸린 문제이다.

DFS알고리즘을 유도하는 기본 문제인듯 하다.

네트워크의 모습이 그래프 구조를 연상케해서 재미있었다.

---

🧠 문제 이해

1번 컴퓨터부터 네트워크상에 연결된 컴퓨터로 바이러스가 퍼진다.

다른 네트워크에 있는 컴퓨터는 감염되지 않는다.

1번 컴퓨터에 의해 감염된 컴퓨터의 갯수를 출력한다.

import sys



n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
	#네트워크 연결을 나타낼 그래프배열
infected = [False] * (n+1)
	#dfs알고리즘에서 사용될 방문확인용 2차원 배열, 
     # 바이러스 컨셉이라서 변수명을 바꿔줬다 ㅋㅋ

for _ in range(m): 
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
 # m개의 노드를 입력받아 그래프배열을 채워준다.

def dfs(x):
    infected[x] = True
    for i in graph[x]:
        if not infected[i]:
            dfs(i)

dfs(1)
#항상 1번 컴퓨터부터 감염되기에 1을 하드코딩했다.

print(infected.count(True)-1) 
 #1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수 를 출력하기위해
  #1번 컴퓨터는 갯수에서 뺀다.

---

쉬워서 재밌던 문제😋