[python] 2606번 - 바이러스

[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을 해주었다.

from http://bang-tori.tistory.com/22 by ccl(A) rewrite - 2021-12-07 18:27:07