백준(BaekJoon) 2606 - 바이러스

# DFS로 문제풀기 

computer = int(input())
line = int(input())

# 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수
# [[], [], []]  
graph  = [[] for _ in range(computer+1)]
visited = [False] * (computer + 1)

# [[], [2,5], [1,3,5], [2], [7], [1,2,6], [5], [4]]

for i in range(computer):
    if i !=0:
        node, num = map(int, input().split())
        graph[node].append(num)
        graph[num].append(node)

        
def dfs(graph, node, visited):
    visited[node] = True       
    for i in graph[node]:
        if not visited[i]:
            dfs(graph, i, visited)
            
    return sum(visited)-1  
            
print(dfs(graph, 1, visited))  # 실패

 

computer = int(input())
line = int(input())

# 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수
# [[], [], []]  
graph  = [[] for _ in range(computer+1)]
visited = [False] * (computer + 1)

# [[], [2,5], [1,3,5], [2], [7], [1,2,6], [5], [4]]

for i in range(line):
    node, num = map(int, input().split())
    graph[node] += [num]
    graph[num] += [node]     
       
def dfs(graph, node, visited):
    visited[node] = True       
    for i in graph[node]:
        if not visited[i]:
            dfs(graph, i, visited)
            
    return sum(visited)-1    
          
print(dfs(graph, 1, visited))    # 성공

 

# 위에것은 왜 실패했을까?!?!  

# 다른점 
for i in range(computer):
    if i !=0:
        node, num = map(int, input().split())
        graph[node].append(num)
        graph[num].append(node)


for i in range(line):
    node, num = map(int, input().split())
    graph[node] += [num]
    graph[num] += [node]

문제는 range로 입력하는 값이 문제였다! 

-  네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수 만큼 돌려줘야 한다

computer = int(input())
line = int(input())

# 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수
# [[], [], []]  
graph  = [[] for _ in range(computer+1)]
visited = [False] * (computer + 1)

# [[], [2,5], [1,3,5], [2], [7], [1,2,6], [5], [4]]

for i in range(line):
    node, num = map(int, input().split())
    graph[node].append(num)
    graph[num].append(node)     
       
def dfs(graph, node, visited):
    visited[node] = True       
    for i in graph[node]:
        if not visited[i]:
            dfs(graph, i, visited)
            
    return sum(visited)-1    
          
print(dfs(graph, 1, visited))    # 성공

# BFS로 문제풀기

from collections import deque

computer = int(input())
line = int(input())
graph = [[] for _ in range(computer+1)]  
visited = [False] * (computer+1)

for i in range(line):
    node, num = map(int, input().split())
    graph[node] += [num]
    graph[num] += [node]
    


def bfs(graph, node, visited):
    queue = deque([node])   # node를 큐에 넣고 
    visited[node] = True   # 큐에 넣어진 노드는 True(방문) 처리 
    
    # 큐가 완전히 빌 때까지 반복      
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:  # false 이면은, 방문처리가 안 되어 있으면 
                queue.append(i) # 큐에 넣고 
                visited[i] = True # 방문 처리 
                
    return sum(visited)-1
                

print(bfs(graph, 1, visited))