Baekjoon 2606 - 바이러스 (Python)

Virus 

---

◎ Problem Definition

2606번: 바이러스

---

◎ Implementation

1. Problem Type 

Graph, DFS (Silver 3)

2. Problem Analysis

1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램. 

- 연결된 노드의 수를 구해야 하기 때문에 visited는 bool 이 아닌 int로 적용했다. 

- 방문 노드를 확인하는 stack을 구성했다. 

3. Solution_1 (☆초기 접근)

▶ 완성 코드 

# bj_2606_Virus
# Feb. 25th, 2022
# by Elie_H


# input : N 
n = int(input())  # num_node, N < 100 
visited = [0] * (n+1)

m = int(input())  # num_edge 
edges = []
for i in range(m):
    edges.append(list(map(int, input().split())))

# group 내 원소가 없을 때까지 edges를 돌며 visited = 0 인 항목을 추가합니다. 
# 첫번째 값 '1' add 
visited[1] = 1
group = [1]

while len(group) != 0 :
    edge = group.pop(0)

    for e1, e2 in edges:
        if e1 == edge and visited[e2] == 0:
            visited[e2] = 1
            group.append(e2)
            continue
        elif e2 == edge and visited[e1] == 0:
            visited[e1] = 1
            group.append(e1)
            continue

# print(visited)
print(sum(visited)-1)

▶ 성능 

• memory : 30864 KB
• time : 72 msec

---

◎ Results

- pop() 함수를 사용하여 간단히 구현했다.

- BFS처럼 재귀적 호출 구조를 적용하면 수행시간이 조금 더 빨라질 것 같다. (시간나면 다시 해보자!!!)