[알고리즘]BOJ_2606_바이러스

#문제 링크

2606번: 바이러스 (acmicpc.net)

2606번: 바이러스

 

#문제

 

#답안1 - DFS

import sys
input=sys.stdin.readline


#dfs함수 생성
def dfs(V) :
    #방문 여부를 표시해줌
    visit[V]=1

    for i in range(1, node+1) :
        #방문하지 않고, 연결정보가 1인 노드에 한에서만 dfs를 호출한다.
        if visit[i] == 0 and matrix[V][i]==1 :
            dfs(i)



#컴퓨터의 개수 즉, 노드의 개수를 입력받음
node=int(input())

#컴퓨터 쌍의 수를 입력받는다.
edge=int(input())

#2차원 인접행렬을 미리 만들어놓는다. ex) 노드의 개수 7이라면 8*8 인접행렬을 만들어놓고 0은 사용 x
matrix=[[0]*(node+1) for _ in range(node+1)]

#한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍을 입력받는다. 동시에 인접행렬에 연결정보를 담는다.
for _ in range(edge) :
    n1, n2=map(int, input().split())
    matrix[n1][n2] = matrix[n2][n1] = 1

#방문여부를 표시할 visit 리스트 생성
visit=[0]*(node+1)

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

 

#답안2 - BFS

import sys
from collections import deque
input=sys.stdin.readline

#bfs함수 생성
def bfs(V) :
    queue=deque()
    #queue에 append해준다.
    queue.append(V)
    # 방문 여부를 표시해줌
    visit[V]=1

    while queue :
        V=queue.popleft() #노드 정보 한개를 pop한다.
        for i in range(1, node+1) :
            if visit[i]==0 and matrix[V][i]==1 : #방문하지 않고, 연결정보가 1인 것들만 queue에 담아준다.
                #큐에 담아준다.
                queue.append(i)
                #방문 여부를 표시해준다.
                visit[i] = 1

#컴퓨터의 개수 즉, 노드의 개수를 입력받음
node=int(input())

#컴퓨터 쌍의 수를 입력받는다.
edge=int(input())

#2차원 인접행렬을 미리 만들어놓는다. ex) 노드의 개수 7이라면 8*8 인접행렬을 만들어놓고 0은 사용 x
matrix=[[0]*(node+1) for _ in range(node+1)]

#한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍을 입력받는다. 동시에 인접행렬에 연결정보를 담는다.
for _ in range(edge) :
    n1, n2=map(int, input().split())
    matrix[n1][n2] = matrix[n2][n1] = 1

#방문여부를 표시할 visit 리스트 생성
visit=[0]*(node+1)



bfs(1)
print(visit.count(1)-1)

 

 

#답안1 & 답안2 풀이

 

😅입력받기 

 

😅dfs로 풀어보기

 

😅bfs로 풀어보기 

 

😅속도, 메모리 비교