[알고리즘][파이썬]2606-바이러스

문제

코드

BFS

import sys
from collections import deque

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph=[[] for _ in range(n+1)]


def bfs(start_v):
    visited=[start_v]
    q =deque()
    q.append(start_v)
    while(q):
        cur_v=q.popleft()
        for v in graph[cur_v]:
            if(v not in visited):
                visited.append(v)
                q.append(v)
    return len(visited)-1


for i in range(m):
    a, b = map(int,sys.stdin.readline().strip().split())
    graph[a].append(b)
    graph[b].append(a)

print(bfs(1))

DFS

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph=[[] for _ in range(n+1)]

visited=[]
def dfs(cur_v):
    visited.append(cur_v)
    for v in graph[cur_v]:
        if(v not in visited):
            dfs(v)
    return len(visited)-1

for i in range(m):
    a, b = map(int,sys.stdin.readline().strip().split())
    graph[a].append(b)
    graph[b].append(a)

print(dfs(1))

문제설명

컴퓨터 네트워크에서 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하는 문제이다.

 

풀이

컴퓨터 네트워크를 이중배열의 그래프형태로 입력받고

1번 컴퓨터 즉, 1번 정점을 시작점으로 DFS나 BFS를 이용하여 연결되어 있는 모든 정점의 갯수를 반환하도록 구현했다.

 

여기서 1번 컴퓨터를 제외한 바이러스 감염 컴퓨터의 수를 원하는 것이기 때문에

마지막 visited의 길이에서 -1을 해줬다.