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

문제풀이

 

그래프 문제는 먼저, 노드와, 간선의 정보를 모두 저장해준다. 이 문제 해결법은 그래프의 1 컴퓨터 노드에서 탐색을 시작했을 때, 1을 제외한 방문했던 노드수를 count 해준다.

 

노드 간의 탐색은 dfs, bfs 둘 중 dfs를 사용하였다. 

 

소스코드

 

import sys

input = sys.stdin.readline

T = int(input())
L = int(input())

road = [[0] * (T+1) for i in range(T)]
visited = [0 for i in range(T)]
for i in range(L):
    a,b = map(int, input().split()) #연결할 노드 2개를 입력
    road[a-1][b-1]=1 #양방향 으로 모두 갈수 있기 때문에 양방향 둘 다 1로 저장한다. 
    road[b-1][a-1]=1

def dfs(v):
    visited[v]=1
    for i in range(T):
        if road[v][i] == 1 and visited[i] == 0: #길이 있고 방문하지 않았다면
            dfs(i)
dfs(0) #1번 컴퓨터에서 탐색시작
count = 0
for i in range(1,T):
    if visited[i]==1:
        count+=1
print(count)

www.acmicpc.net/problem/2606

2606번: 바이러스