백준 2606번 바이러스 파이썬 DFS

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

답안

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
n = int(input())
m = int(input()) 
visited = [False] * (n+1)
graph = [[] for _ in range(n+1)]
lst = []
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(1,n+1):
    graph[i].sort()

dfs(graph, 1, visited)
print((visited.count(True))-1)

 

---

 

• 예제를 대입해서 생각해 보자.

 

7
6
1 2
2 3
1 5
5 2
5 6

• 그림으로 그려 보면

노란색 형광펜으로 연결된 부분을 세면된다.

결국 방문 노드 수를 계산하면 되는 문제로 해석을 할 수 있다.

 index                  0           1         2        3        4        5        6        7

 

• 최종적으로 1을 제외한 방문 노드 수를 세면 되므로 총 True의 개수 - 1을 하면 답을 도출 해낼 수 있다.

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