[백준] 2606 바이러스 파이썬 풀이(DFS와 BFS)

 

문제

• 컴퓨터끼리 연결된 쌍이 주어진다.
• 1번 컴퓨터가 웜 바이러스에 걸렸을때 연결된 모든 컴퓨터가 웜 바이러스에 걸린다.
• 바이러스에 걸리는 컴퓨터의 수를 출력해라

 

문제풀이

• DFS로 푼다.
• 연결되어있는 노드를 끝까지 탐색해야하기 때문.
• 2차원 배열에 연결되어있는 값을 저장한다.
• 1번 노드에 연결된 모든 값을 visited_dfs에 저장하고 1번의 뺀 개수를 출력한다.

코드

 

# 정점의 연결정보 입력받기
n= int(input()) #정점
m = int(input()) #연결수
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
 
visited_dfs = []
 
def dfs(graph, cur_node, visited):
    # 현재 노드를 방문처리
    visited.append(cur_node)
    graph[cur_node].sort()
    # 현재 노드와 인접한 노드를 확인
    for link_node in graph[cur_node]:
        # 방문하지 않은 노드라면 재귀호출
        if link_node not in visited:
            dfs(graph, link_node, visited)
 
dfs(graph, 1, visited_dfs)
print(len(visited_dfs)-1)