[백준 / 2606] 바이러스 - Python

너비 우선 탐색(BFS)을 이용하여 풀었으므로, 해당 알고리즘을 선행하면 좋다.

 

2021.03.19 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 너비 우선 탐색(BFS) - Python

[보기 쉬운 Algorithm] 너비 우선 탐색(BFS) - Python

 

입력을 받아 양방향 그래프를 작성하고, 너비 우선 탐색으로 1번 노드부터 탐색한다.

<입력 1>

N = int(input())
M = int(input())

 

총노드의 개수인 N개와 간선의 개수인 M을 입력받는다.

<그래프 선언>

graph = {}
for i in range(1, N+1):
    graph[i] = []

 

간선이 존재하지 않는 그래프도 있을 수 있으니 노드의 개수만큼 딕셔너리 형태로 모든 노드의 키(key)를 만들어 준다. 값(value)은 빈 리스트를 선언한다.

<입력 2>

for _ in range(M):
    x, y = map(int, input().split())

    graph[x].append(y)
    graph[y].append(x)

 

연결되는 두 노드인 x, y를 입력받는다. 해당 노드는 양쪽이 모두 연결되므로 x 노드와 y 노드에 모두 각각 추가해준다.

<BFS>

def bfs(graph, first_node):
    visit = []
    queue = []

    queue.append(first_node)

    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])

    return visit

 

1번 노드와 연결된 모든 노드를 찾기 위해서 너비 우선 탐색을 한다.

방문한 노드는 visit에 넣고, 앞으로 방문할 노드는 queue에 넣는다. 처음 노드를 queue에 넣는다.

queue가 사라질 때까지 while문을 반복하고, node를 queue에서 빼온다. 방문했던 노드라면 넘어가고, 방문하지 않은 노드인 경우 방문한 노드로 바꾸고, 연결된 노드를 queue에 넣어준다.

 

방문한 노드가 담겨있는 visit를 반환한다.

<호출 및 출력>

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

 

생성한 bfs함수를 호출하면 1번 노드를 포함한 방문 노드가 반환되므로 총개수에서 1을 빼준 값을 출력한다.

 

<전체 코드>

def bfs(graph, first_node):
    visit = []
    queue = []

    queue.append(first_node)

    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])

    return visit


N = int(input())
M = int(input())

graph = {}
for i in range(1, N+1):
    graph[i] = []

for _ in range(M):
    x, y = map(int, input().split())

    graph[x].append(y)
    graph[y].append(x)

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