[알고리즘][백준 2606] 바이러스

문제 링크

백준 2606 바이러스 문제 링크

문제 정의

입력
노드 개수(N), 간선 개수(M) 입력 받고,
간선 입력
ex)
7(노드 개수)
6(간선 개수)
1 2
2 3
1 5
5 2
5 6
4 7

출력
1번 노드와 연결된 노드들의 수를 출력
ex)
4

문제 풀이

graph를 만든다.
graph[a] = [x,y,z]이면, a노드에서 연결된 노드가 x, y, z라는 뜻이다.

위의 공식에 따라 graph[1] ~ graph[N]을 만든다.
탐색한지 안한지 확인하는 visit[N] 변수를 만든다.
graph[1]을 탐색하고, visit[1]을 True로 바꾼다.
graph[1]의 원소들을 인덱스로 하는 graph들도 탐색하고, visit[x]를 True로 바꾼다.
위와 같은 과정을 반복한다.

더이상 방문할 곳이 없으면, visit값을 확인 한다.
visit[0]과 visit[1]을 제외한 나머지 True값들의 count를 출력한다.

내 코드

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[0] * n for i in range(n+1)]
visit = [False]*(n+1)
visit[0]=True

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



def dfs(graph, i):
   
    visit[i]=True
    for i in graph[i]:
        if visit[i]==False:
            dfs(graph, i)

dfs(graph, 1)
print(visit.count(True)-2)