[2606] 바이러스

2606번: 바이러스

 

www.acmicpc.net

---

🤔 문제 설명

[2606] 그림 1 (출처 : 백준)

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

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자.

 

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

 

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

 

🤨 제한 사항

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

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

 

😀 입출력 예

입력	출력
7 6 1 2 2 3 1 5 5 2 5 6 4 7	4

 

👩‍🔧 사용 메서드 및 속성

sys.stdin.readline()	사용자로부터 한 줄의 입력을 받습니다.
split()	문자열을 나눠서 배열로 반환합니다.
append()	리스트 끝에 요소를 추가합니다.
get()	딕셔너리에서 key값으로 value값을 찾을 수 있습니다.
pop()	리스트 맨 끝의 요소를 제거하고 값을 반환합니다.

 

👩‍🏫 어떻게 풀어요?

 

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

 

전형적인 스택을 사용한 DFS 문제입니다.

 

번호가 낮은 순으로 방문하라는 말이 없었으므로, 그냥 스택에 넣고 빼는 순으로 하위 노드까지 찾아가는 방식을 사용하였습니다. 

저는 딕셔너리에 경로를 넣어서 풀었습니다.

 

먼저 스택에 시작지점 번호인 1번을 넣고, 1번에서 갈 수 있는 노드를 전부 스택에 넣습니다.

그 다음, 맨 앞에 있는 번호를 pop()하고 그 노드에서 갈 수 있는 다음 경로를 탐색합니다. 이때, stack과 visited 배열에 들어가 있지 않아야 합니다. 만약 있다면 그건 이미 바이러스가 감염된 컴퓨터이기 때문이죠.

이 과정을 스택에 내용이 없을 때까지 반복합니다.

 

마지막에 -1을 한 이유는, 1번 노드까지 visited 배열에 들어가 있어서 그렇습니다. 1번 컴퓨터를 통해 감염된 컴퓨터 숫자만 뽑으면 되니까 visited 배열 길이에서 -1을 하면 되겠죠?

 

 

 

👾트리스티의 답

import sys
 
# 스택을 이용한 DFS
 
computerNum = sys.stdin.readline().split()
relation = sys.stdin.readline().split()
 
node = {}
visited = []
for i in range(int(relation[0])) :
    f, t = map(int, sys.stdin.readline().split())  
    
    if node.get(f) == None :
        node[f] = [t]
        if node.get(t) == None :
            node[t] = [f]
        else :
            node[t].append(f)
 
    else :
        node[f].append(t)
        if node.get(t) == None :
            node[t] = [f]
        else :
            node[t].append(f)
 
 
def stackDFS(node, start) :
    global visited
    stack = [start]
 
    while stack :
        nodePoint = stack.pop()
        visited.append(nodePoint)
        for i in node[nodePoint] :
            if i not in stack and i not in visited :
                stack.append(i)
        
 
    return visited
 
stackDFS(node, 1)
print(len(visited) - 1)

 

※ 잘못된 정보가 있거나 수정사항이 있다면 댓글로 남겨주세요!