[python] 2606번 - 바이러스

문제

파이썬 풀이

이 문제는 1번부터 연결되어있는 모든 노드를 탐색하는 문제이다.

dfs와 bfs 내용 공부를 할 때 전체 탐색에 있어서는 dfs를 사용한다는 내용이 떠올라 dfs를 적용시켜 문제를 풀었다.

앞에 1260번 문제에서 이미 기본적인 dfs와 bfs를 구현했던 터라 코드 내용을 조금만 바꾸면 돼서 쉽게 풀 수 있었다.

import sys
input = sys.stdin.readline

e = int(input().rstrip())
v = int(input().rstrip())
graph = [[0]*(e+1) for _ in range(e+1)]
visited = [0] *(e+1)

def dfs(node) :
    visited[node] = 1
    for i in range(1, e+1) :
        if visited[i]==0 and graph[node][i]==1 :
            dfs(i)

for _ in range(v) :
    a, b = map(int, input().rstrip().split())
    graph[a][b] = graph[b][a] = 1

dfs(1)
print(visited.count(1)-1)

이번에도 그래프는 인접행렬로 구현하였고, 이전 문제에서는 과정을 출력한다면, 이번 문제는 연결되어있는 노드의 수를 출력해야 하기에 과정을 출력하는 print문을 지우고 탐색을 마친 후 방문한 노드에 대해 카운팅을 하였다.

탐색을 마친 후 방문한 노드는 visited리스트 해당 인덱스의 값이 1로 되어 있다. 따라서 visited리스트에서 1의 개수를 카운팅 하고, 1번 노드 자신은 연결 노드 수에 포함시키지 않기 때문에 -1을 해주었다.