[백준] 2606번 : 바이러스 (파이썬)

문제

나의 답안

n=int(input())
m=int(input())
g=[[] for i in range(n+1)]#n+1개의 노드를 갖는 그래프 생성

for i in range(m):
    a,b=map(int,input().split())
    g[a].append(b)#a노드에 b연결
    g[b].append(a)#b노드에 a연결

visited=[0]*(n+1) #방문한 노드 저장, 방문했으면 1로 변경

def dfs(n):
    visited[n]=1
    for i in g[n]:
        if visited[i]==0:#방문하지 않았다면
            dfs(i)#방문처리
    return sum(visited)#방문한 노드 수(1의 개수)

print(dfs(1)-1)#1번을 제외한 컴퓨터 수

접근 방법

• 1번 컴퓨터부터 접근하므로 n+1개의 노드를 갖는 그래프를 생성한다.
• 이후 반복문을 통해 각 쌍을 연결하는 간선을 생성해준다.
• 방문한 노드는 1로 저장하고, 아닌 노드는 0으로 간주한다.
• dfs 함수에선 방문한 노드인지 판별해주고, 방문한 노드의 수를 반환해준다.
• 감염된 컴퓨터의 개수에선 1은 포함되지 않으므로 -1을 해준다.