[백준] 2606. 바이러스 (실버3, Python)

풀이

1번 컴퓨터와 연결되어 있는 모든 컴퓨터의 개수를 찾으면 된다. 연결되어 있는 모든 노드를 구하기 때문에 BFS와 DFS 둘 다 상관없다고 판단했다.

 

입력값 초기화

 

num: 컴퓨터 개수

networkCount: 네트워크 상에 연결된 컴퓨터 쌍의 수

 

networkInfo: 연결되어 있는 다른 컴퓨터의 번호 저장

* networkInfo[n]에 n과 연결된 컴퓨터 번호가 저장되어 있다

networkCheck: 각 컴퓨터를 확인했는지 여부 저장 값

 

 

 

 

 

networkCount 만큼 데이터를 입력받아 networkInfo에 각 컴퓨터 번호와 연결되어 있는 다른 컴퓨터 번호를 저장한다.

편의성을 위해 num+1만큼의 크기를 잡고 0번째 원소는 사용하지 않는다.

1번 컴퓨터와 연결된 컴퓨터 수를 구하기 때문에 무조건 1번부터 시작한다. 따라서 networkCheck[1]에 True 값으로 초기화 후, 각 함수를 실행한다

 

 

BFS 활용

BFS이기에 큐를 활용하여 구현했다. 큐에는 1번 컴퓨터와 연결된 다른 컴퓨터 번호를 저장할 용도이다. 큐의 원소가 없어질때까지 반복하며 큐에 원소가 더이상 없다는 것은 더이상 확인하지 않은 1번 컴퓨터와 연결된 컴퓨터가 없다는 의미이다.

 

먼저 큐에 1를 저장한다.

while문에서 큐를 하나 빼서 해당 컴퓨터 번호와 인접하면서  아직 방문하지 않은 노드는 아래 작업을 수행한다.

1. 결과값 +1

2. 큐에 인접 노드 저장

3. 인접 노드 방문 설정

 

이 과정을 반복하면 결과값을 구할 수 있다.

 

 

DFS 활용

DFS이기에 스택을 활용하여 구현했다. 여기서 스택의 BFS의 큐와 동일한 의미이며 result값을 구하는 과정 역시 동일하다.

 

 

 

최종코드

import queue

def checkVirusBFS():
    result = 0
    networkQueue = queue.Queue()
    networkQueue.put(1)
    
    while networkQueue.qsize() > 0:
        computer = networkQueue.get()
        
        for node in networkInfo[computer]:
            if not networkCheck[node]:
                result+=1
                networkQueue.put(node)
                networkCheck[node] = True
    
    print(result)

def checkVirusDFS():
    result = 0
    networkStack = []
    networkStack.append(1)
    
    while len(networkStack) > 0:
        computer = networkStack.pop()
        
        for node in networkInfo[computer]:
            if not networkCheck[node]:
                result+=1
                networkStack.append(node)
                networkCheck[node] = True
    
    print(result)

num = int(input())
networkCount = int(input())

networkInfo = [[] for _ in range(num+1)]
networkCheck = [False] * (num+1)

for i in range(networkCount):
    a, b = map(int, input().split())
    networkInfo[a].append(b)
    networkInfo[b].append(a)

networkCheck[1] = True
checkVirusDFS()
# checkVirusBFS()

 

 

백준 문제

https://www.acmicpc.net/problem/2606

 

Github

https://github.com/ujin302/CodingTest_2023/blob/main/Code/BackJun/silver/s3/s3_2606.py