[백준] 2606. 바이러스

1번 컴퓨터를 통해 바이러스에 걸리는 컴퓨터의 수를 구하는 문제로 다시 해석하면 1번과 직, 간접적으로 연결된 컴퓨터를 탐색해 그 수를 출력하는 문제다. bfs, dfs 중 아무거나 사용해도 되겠지만 이번에는 bfs를 사용했다.

from collections import deque
from sys import stdin

def bfs(start_node):
    global count
    q = deque()
    q.append(start_node)
    visited[start_node] = True
    while q:
        v = q.popleft()
        for n in graph[v]:
            if not visited[n]:
                q.append(n)
                visited[n] = True
                count += 1
    

num_of_com = int(stdin.readline())
num_of_node = int(stdin.readline())

graph = [[] for _ in range(num_of_com+1)] #노드 번호와 인덱스를 맞추기 위해 사용하지 않는 노드 1개 추가
visited = [False] * (num_of_com+1)
count = 0

for i in range(num_of_node):
    info = list(map(int, stdin.readline().split()))
    graph[info[0]].append(info[1])
    graph[info[1]].append(info[0])
    

bfs(1)
print(count)

32460 kb

88 ms

크게 아래의 조건만 떠올릴 수 있다면 문제를 풀 수 있다.

 

1. 주어진 정보로 그래프를 만든다.

2. 방문을 했는지 확인할 bool 배열(리스트)를 만든다.

3. BFS를 통해 탐색하면서 새로운 노드를 방문 할 때마다 count + 1 해준다.

4. 마지막에 count를 print( ) 해준다.

 

아래 두 코드는 공부를 하기 위해 가져온 상위 답안자의 답이다.

import sys


def dfs(n):
    Heap.append(n)
    for v in V[n]:
        if v not in Heap:
            dfs(v)


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

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

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

dfs(1)

print(len(Heap) - 1)

29200 kb

64 ms

 

import sys
_=input();T={};V=[0]*101
def D(k):
 while T[k]:
  t=T[k].pop()
  if not V[t]:V[t]=1;D(t)
A={(*map(int,sys.stdin.readline().split()),) for i in range(int(input()))}
for a in A:
 for i in [0,1]:T.setdefault(a[i],[]).append(a[1-i])
try:
 while T[1]:D(T[1].pop())
except:pass
print(sum(V[2:]))

29200 kb

64 ms