[백준] 바이러스

최동혁·2022년 12월 6일

baekjoon python 알고리즘

백준

목록 보기

33/68

바이러스

solved_ac[Class3][바이러스](https://www.acmicpc.net/problem/2606)

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1

예제 출력 1

문제 해석

붙어 있는 모든 노드의 수를 세는 문제이다. DFS와 BFS 둘다 이용해서 풀어도 되지만 나는 DFS로 풀었다. [백준]1260번: DFS와 BFS에서 설명을 했지만 DFS와 BFS의 차이점과 어떤 문제 유형에서 어떤 알고리즘을 써야하는지에 대해서 알아보자.

DFS와 BFS 비교

images_lucky-korma_post_e2ef7ac3-14e6-42e7-a768-224c5f773e29_R1280x0-3

DFS와 BFS 시간복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있다.

그래프의 모든 정점을 방문하는 것이 주요한 문제
- 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없다. 둘 중 편한 것을 사용하면 된다.
경로의 특징을 저장해둬야 하는 문제
- 예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다)
최단거리 구해야 하는 문제
- 미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리하다. 왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문이다.

이밖에도 검색 대상 그래프가 정말 크다면 DFS를 고려하고, 검색대상의 규모가 크지 않고 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS를 고려한다.

풀이

방문을 했을시에 방문 처리를 위한 visited boolean 변수와 graph 리스트를 입력받는다.
index는 0부터 시작하기 때문에 헷갈릴수 있어서 노드 번호와 같게끔 0번은 비워주고 시작한다.
방문을 했다면 visited가 True이다. 방문을 했다면 dfs 함수가 한번 호출된 것이기 때문에 방문한 노드의 번호를 인덱스로 visited 변수를 True로 만들어주고 해당 노드 행의 graph를 탐색한다.
해당 노드와 이어져 있는 노드들의 방문 변수가 False이면 이어져 있지만 아직 방문을 안한것이기 때문에 해당 노드에서 dfs 함수를 호출해준다.
처음 시작은 1번 노드로 시작한다.
함수 호출이 다 끝이나고 visited 변수를 살펴보면 처음 1번 노드로 시작을 했기 때문에 1번 노드의 방문 변수가 True이다. 하지만 우리는 1번 변수를 제외한 노드들의 방문 여부가 궁금하기 때문에 1번 노드는 제외한다.

import sys

N = int(sys.stdin.readline())

M = int(sys.stdin.readline())

visited = [False] * (N + 1)

graph = [[] for _ in range(N + 1)]

for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
    
    
count = 0

def dfs(graph, visited, v):
    visited[v] = True
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, visited, i)
 
dfs(graph,visited, 1)  
        
count = 0          
for i in visited:
    if i == True:
        count += 1
print(count - 1)

결론

이 문제는 dfs로 풀어도 되고 bfs로 풀어도 된다. 둘 다 시간은 거의 비슷하게 걸리는데, 보통 dfs는 모든 노드를 다 방문해야 하는 경우 더 많이 쓴다. 이 문제도 최소한의 비용을 따지는 것이 아닌 총 몇번 방문했냐. 즉 모든 노드를 다 방문을 해야되기 때문에 dfs를 이용하여 풀었다. 바로 전 문제 2178번은 미로를 탐색하면서 최소 비용으로 결승점에 가는 것이기 때문에 굳이 모든 노드를 다 방문하지 않고도 답에 도달할 수 있다. 그래서 bfs로 푼 것이다.