[#2606] 바이러스

문제

#2606 바이러스
Silver3
적용 알고리즘: BFS(너비 우선 탐색) 알고리즘

---

풀이 방법

• 그래프를 그린 뒤, 이동한(간선)의 횟수를 샌다.
• 이동 횟수를 세는 cnt 변수를 global로 지정하여, 함수 내에서의 숫자 변동이 외부에 반영되게끔 한다.

코드 흐름

1. 입력받은 수를 2차원 리스트로 그래프화 한다.
2. 깊이 우선 탐색 알고리즘을 사용하고, 노드 이동 횟수를 저장한다.

코드

def dfs(graph, v, visited):
    global cnt
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            cnt += 1
            dfs(graph, i, visited)

n = int(input())
k = int(input())

visited = [False] * (n + 1)
com = [[] for i in range(n + 1)]
cnt = 0

# 그래프를 만드는 과정
for i in range(k):
    a, b = map(int, input().split())
    com[a].append(b)
    com[b].append(a)

dfs(com, 1, visited)
print(cnt)

체감 난이도: 4.2/5
DFS의 알고리즘을 코드로 구성할 수 있으면 쉽게 풀 수 있는 문제였다. 다만 bfs 함수 내에서 노드 이동을 어떻게 셀 것이냐가 관건이었는데, 이는 global변수를 사용하여 해결하였다.