백준 2606번 : 바이러스 python 문제 풀이 (bfs 알고리즘)

 

백준 2606 문제입니다.

 

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

2606번: 바이러스

 

 

 

문제 보기의 그래프를 1을 중심으로 다시 그려보면 이와 같아집니다. 1번 컴퓨터가 바이러스가 걸렸을 때, 같이 걸린 컴퓨터의 수를 구하는 문제였습니다. 

 

입력

문제의 입력은 [ [ ] , [ 2 , 5 ] , [ 1 , 3 , 5 ] , [ 2 ] , [ 7 ] , [ 1 , 2 , 6 ] , [ 5 ] , [ 4 ] ] 이와 같이 이차원 배열의 형태로 받을 예정입니다.

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

 

출력

4

 

 

 

저는 bfs를 사용하여 문제를 해결했습니다. bfs나 dfs 둘 중 하나 편하신 것을 골라서 문제 푸시면 됩니다.

 

computer = int(input())
n = int(input())

node_visited = [[] * _ for _ in range(computer + 1)]

for i in range(n):
    a, b = map(int, input().split())
    node_visited[a].append(b)
    node_visited[b].append(a)


def bfs(node_visited,start):
    visited, need_visited = [], []
    need_visited.append(start)

    while need_visited:
        node = need_visited[0]
        del need_visited[0]

        if node not in visited:
            visited.append(node)
            need_visited.extend(node_visited[node])
    return visited


print(len(bfs(node_visited,1)) - 1)

 

extend() 함수는 [1, 2, 3] 과 같이 리스트 형태로 존재하여도 리스트 안에 넣을 때, 1, 2, 3 의 형태로 분리되어 넣어주는 함수입니다. 

append() 함수는 [1, 2, 3] 이면 [1, 2, 3] 으로 삽입됩니다.