[Python] 백준 #2606번: 바이러스

즉 감염당한 컴퓨터를 제외한 감염당한 컴퓨터들 개수를 출력하는 코드를 짜면 됨.

---

걸림돌

• 위 문제를 풀기위해서 배열이나 리스트를 이용하여 풀어보려고 했으나 너무 복잡해서 실패함
  • 너비 우선 탐색( BFS(Breadth Frist Search) )를 이용하여 쉽게 해결함

---

코드

computer_num = int(input())
graph = [[] for _ in range(computer_num + 1)]

pair_num = int(input())

for _ in range(pair_num):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

    # 너비 우선 탐색 알고리즘을 `dfs`함수로 만듬
def dfs(graph, s):
    visited = list()    # 방문한 노드를 담을 배열
    stack = list()  # 정점과 인접한 방문 예정인 노드를 담을 배열

    stack.append(s) # 처음에는 시작 노드를 담고 시작

    while stack:    # 더이상 방문할 노드가 없을 때 까지 반복
        node = stack.pop()  # 방문할 노드를 앞에서 부터 하나씩 꺼내기

        if node not in visited: # 방문한 노드가 아니라면?
            visited.append(node)    # vsited 배열에 추가
            stack.extend(reversed(graph[node])) # 해당 노드의 자식노드로 추가함
    return visited

result = dfs(graph, 1)  # 함수를 실행하여 `result`변수에 리턴 값을 넣어줌
print(int(len(result))-1)   # 감염된 컴퓨터를 제외한 컴퓨터의 숫자를 출력해야하기 때문에
                            # `result`에서 -1 한 값을 출력

 

너비 우선 탐색 (BFS)

너비 우선 탐색은 너비를 깊이보다 우선적으로 탐색하는 방법. 처음에 최대한 옆으로 넓게 이동한 후 더이상 옆으로 갈 수 없으면 아래로 이동하는 방식.

 

다음과 같은 특징이 있음

• 최단 경로를 찾고자 할 때 사용함 : 수평으로 탐색하기 때문에 최단 경로를 중간에 찾을 수가 있음
• 비교적으로 멀리 떨어져있는 구역 사이의 관계를 알고 싶을 때 깊이 우선 탐색 (DFS)의 경우 모든 경우를 고려해야 할 상황을 더 빠르게 찾아낼 수 있음
• 큐를 이용하여 구현함