[Python]DFS와BFS 백준 2606

 문제

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

해당 노드에 연결된 모든 노드들을 찾는문제라고 볼수있다.

DFS를 통해 구현해보자.

import sys
N=int(sys.stdin.readline())#컴퓨터수
M=int(sys.stdin.readline())#연결수
matrix=[[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    x,y=map(int,sys.stdin.readline().split())
    matrix[x][y]=1
    matrix[y][x]=1
 
#current_node:시작 컴퓨터,matrix:인접행렬,virus_com:바이러스 걸린컴퓨터터
def dfs(current_com,matrix,virus_com):
    virus_com+=[current_com]#바이러스 걸린 컴퓨터 저장
    for search_node in range(len(matrix[current_com])):  # 연결된 컴퓨터 탐색
        if matrix[current_com][search_node] and search_node not in virus_com:  # 연결되어 있고 바이러스에 걸리지 않았다면
            virus_com = dfs(search_node, matrix, virus_com)  # 해당컴퓨터에서 다시 재귀로 실행
    return virus_com
 
 
print(len(dfs(1,matrix,[]))-1)#1번을 제외한 바이러스가 걸린 컴퓨터수