웜 바이러스[백준 2606]

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

7

6

1 2

2 3

1 5

5 2

5 6

4 7

예제 출력

4

 

#코드( 1이랑 이어지는 경우가 없는 경우도 처리해야 한다.) DFS

import sys
 
def DFS(x):
  global totalCnt
  visited[x] = True 
  if myGraph[1][0] == 0 and len(myGraph[1]) == 1: return
  
  for i in range(len(myGraph[x])):
    if x == 1 and i == 0: continue
    y = myGraph[x][i]
    if visited[y] == False:
      totalCnt += 1
      DFS(y)
  
  
 
if __name__ == "__main__":
  myGraph = {}
  n = int(sys.stdin.readline())
  m = int(sys.stdin.readline())
  visited = [False]*1000
  totalCnt = 0
  
  try : myGraph[1].append(0)
  except :
    myGraph[1] = list()
    myGraph[1].append(0)
    
  for i in range(m):
    a, b = map(int, sys.stdin.readline().split()) 
      
    try : myGraph[a].append(b)
    except : 
      myGraph[a] = list()
      myGraph[a].append(b)
      
    try : myGraph[b].append(a)
    except : 
      myGraph[b] = list()
      myGraph[b].append(a) 
      
  DFS(1) 
  print(totalCnt)

import sys
 
def dfs(x):
  global myGraph, visited, totCnt
  
  visited[x] = True
  
  for i in range(len(myGraph[x])):
    x2 = myGraph[x][i]
    if visited[x2] == False:
      totCnt+=1
      dfs(x2)
  
 
if __name__=="__main__":
  input   = sys.stdin.readline
  N       = int(input())
  M       = int(input())
  myGraph = [[] for _ in range(N+1)]
  visited = [False]*(N+1)
  totCnt  = 0
  
  for _ in range(M):
    a, b = map(int, input().split())
    myGraph[a].append(b)
    myGraph[b].append(a)
  
  dfs(1)
  print(totCnt)

 

 

# 코드 BFS

import sys
from collections import deque
 
def BFS():
  global cnt
  check = [False]*1000
  deq = deque()
  deq.append(1)
  check[1] = True
  
  while len(deq) > 0:
    cur = deq.popleft() 
    cnt += 1
    for i in range(len(myGraph[cur])):
      if cur == 1 and i == 0: continue
      
      next = myGraph[cur][i]
      if check[next] == False:
        check[next] = True
        deq.append(next)
  
 
if __name__ == "__main__":
  myGraph = {}
  n = int(sys.stdin.readline())
  m = int(sys.stdin.readline())
  cnt = -1
  myGraph[1] = list()
  myGraph[1].append(0)
  
  for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    
    try : myGraph[a].append(b)
    except: 
      myGraph[a] = list()
      myGraph[a].append(b)
      
    try : myGraph[b].append(a)
    except: 
      myGraph[b] = list()
      myGraph[b].append(a)
   
  BFS()  
  print(cnt)

 

# 코드(BFS) 복습

import sys
from collections import deque
 
def BFS():
  global N, myGraph
  
  deq     = deque()
  deq.append(1)
  visited    = [False]*(N+1)
  visited[1] = True
  
  while deq:
    x = deq.popleft()
    
    for i in myGraph[x]:
      if not visited[i]:
        visited[i] = True
        deq.append(i)
  cnt = -1
  for i in visited:
    if i:
      cnt+=1
  print(cnt)
 
if __name__ == "__main__":
  input = sys.stdin.readline
  
  N       = int(input())
  M       = int(input())
  myGraph = [[] for _ in range(N+1)]
  
  for _ in range(M):
    a, b = map(int, input().split())
    
    myGraph[a].append(b)
    myGraph[b].append(a)
  
  BFS()