[Python] 바이러스 # 2606

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

< 문제 풀이 아이디어>

 

1. 시작 정점에서 시작하여 방문한 노드의 수를 구하면 된다.

2. 주어진 컴퓨터의 수가 적으므로, DFS가 더 효율적이다.

 

 

< 코드 >

n = int(input())
m = int(input())
adj = [[] for _ in range(n + 1)] # 경로를 저장하기 위한 2차원 리스트 정점은 1부터 시작하므로 범위는 n + 1까지
visited = [False] * (n + 1)      # 방문한 정점을 담을 리스트를 역시 1부터 시작하므로 n + 1 갯수만큼 False로 설정
count = 0                        # 다녀간 정점을 확인하기 위한 count 변수

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y) # 양방향 그래프로 인접한 정점을 연결 (ex. 정점 1 -> 2 즉, [v0 [], v1 [2], v2 []...])
    adj[y].append(x) # 위와 반대로 적용 (ex. 정점 2 -> 1 즉, [v0 [], v1 [], v2 [1]...])

def dfs(now_pos):
    global count                  # 전역 변수 count를 사용하겠다고 설정
    
    visited[now_pos] = True       # 인자로 들어간 시작 정점 부분은 방문한 리스트에 넣어 True로 만듦
    for next_pos in adj[now_pos]: # ex) adj[1]의 요소는(연결된 정점은) [2, 5]이므로 2, 5를 차례대로 next_pos에 넣어 반복
        if not visited[next_pos]: # next_pos에 해당하는 방문 리스트의 위치가 True가 아니라면
            count += 1            # 맨 처음 시작 정점을 제외하고 거쳐간 노드를 카운트해야 하므로 다음 노드부터 count + 1
            dfs(next_pos)         # next_pos를 시작 정점으로 하여 재귀적으로 dfs 호출

dfs(1)
print(count)