[백준] [python] 2606: 바이러스

---

바이러스 성공출처분류

문제

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

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

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

입력

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

출력

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

 

---

 

풀이 

 

BFS로 구현을 하였다.

초등부 문제였기에 난이도는 쉬운 편이나, 양방향을 간과해서 틀렸다.

 

def solution(adj, visited, start):
    visited[start] = True
    q = [start]
    while q :
        n = q.pop()
        temp = adj[n]
        for i in temp:
            if visited[i] == False:
                visited[i] = True
                q.append(i)
    return visited.count(True)

node = int(input())
edge = int(input())
adj = [ [] for _ in range(node + 1)]
visited = [False] * (node + 1);
for i in range(edge):
    a, b = map(int, input().split())
    adj[a].append(b)
    
print(solution(adj, visited, 1))

 

위의 코드는 adj에 단방향으로 저장된다. 

예제 입력의 결과 adj는 [ [], [2, 5],  [3], [], [7], [6] ] 이렇다. 

 

그런데, 2, 5에서 1로 방향을 바꾸어본다면 어떻게 될까?

adj는 [ [], [], [1, 3], [], [7], [1, 2, 6], [], [] ] 가 된다. 

이 경우, adj[1]가 빈 리스트이기 때문에, 연결이 되어있음에도 불구하고 바이러스를 퍼뜨릴 수 없다.

코드 상으로 보면 while문을 빠져나와 0을 return한다.

 

def solution(adj, visited, start):
    visited[start] = True
    q = [start]
    while q :
        n = q.pop()
        temp = adj[n]
        for i in temp:
            if visited[i] == False:
                visited[i] = True
                q.append(i)
    return visited.count(True) - 1

node = int(input())
edge = int(input())
adj = [ [] for _ in range(node + 1)]
visited = [False] * (node + 1);
for i in range(edge):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a) # 양방향으로 감염이 가능해지게 추가 

print(solution(adj, visited, 1))

 

무방향이기에, 2 5, 5 1을 입력으로 받더라도, 연결이 되어있기에 전염을 시킬 수 있다.

adj[b].append(a)를 추가하면, adj는 [ []. [2, 5], [1, 3, 5], [7],], [5], [4] ]가 된다. 

 

 

고찰

무방향성 그래프에서의 adj, 방향성 그래프에서의 adj는 기본적임에도 헷갈렸다.

그 결과, 시간이 예상보다 많이 소요되었다. 

기본이 새삼 중요하다는 것을 깨닫는다.