[백준_python] 바이러스 || 2606

www.acmicpc.net/problem/2606

2606번: 바이러스

알고리즘 분류에 깊이 우선 탐색과 너비 우선 탐색이 있었는데, 나는 네트워크라는 단어를 읽자마자 DFS보다는 BFS로 구현을 하고 싶다는 생각을 하게 되었다.!

1260을 풀면서 사용했던 bfs를 참고하면서 문제를 풀었는데, 무한 루프에 빠져서 한동안 헤어나올 수가 없었다..
정말 똑같이 적었는데 왜 무한 루프에 빠졌는지 모르겠다. 다시 지우고 작성을 해서 빠져나오긴 했지만,, 아직도 이유를 모르겠다 ㅠ 다음에도 무한 루프에 빠지면, 어느 부분에서 빠지게 된 것인지 원인 파악을 좀 해주어야 할 것 같다.!
 

BFS 너비 우선 탐색

# 바이러스 (bfs 너비우선탐색)

n = int(input())  # 컴퓨터의 수(정점의 개수)
m = int(input())  # 연결된 쌍의 수(간선의 개수)
graph = [[0]*(n+1) for _ in range(n+1)]  # 인덱스값을 간선으로 생각
visited = [False] * (n+1)  # 정점을 방문하였는지
count = 0  # 바이러스 걸린 컴퓨터의 수

for i in range(m):
    a, b = map(int, input().split(' '))
    graph[a][b] = graph[b][a] = 1  # 둘 사이가 연결되어있다면 1


def BFS(start):
    queue = [start]  # 큐 이용
    visited[start] = True
    while queue:
        start = queue.pop(0)
        for i in range(1, n+1):
            if not visited[i] and graph[start][i] == 1:
                queue.append(i)
                visited[i] = True


BFS(1)
for i in visited:
    if i:
        count += 1
print(count-1)

---

DFS 깊이 우선 탐색

# 바이러스 (dfs 깊이우선탐색)

n = int(input())
m = int(input())
graph = [[0]*(n+1) for _ in range(n+1)]
visited = [False] * (n+1)
count = 0

for i in range(m):
    a, b = map(int, input().split(' '))
    graph[a][b] = graph[b][a] = 1


def DFS(start):
    visited[start] = True
    for i in range(1, n+1):
        if not visited[i] and graph[start][i] == 1:
            DFS(i)


DFS(1)
for i in visited:
    if i:
        count += 1
print(count-1)

 
 
 
 
 
 
 
추가로 dict를 이용하는 DFS와 BFS를 보게 되었는데, 이 방법도 괜찮은 것 같다!
chancoding.tistory.com/60

[파이썬] 백준 2606번 바이러스 - BFS방식과 DFS 방식 비교