백준 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번 컴퓨터는 갯수에서 뺀다.
쉬워서 재밌던 문제😋
Author And Source
이 문제에 관하여(백준 2606 문제 풀이 python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mauserne/백준-2606-문제-풀이-python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)