[백준] 2606번 바이러스 파이썬

DFS와 관련된 문제를 풀고자 해당 유형의 문제들 중에서 그나마 난이도가 낮은 녀석을 골라보았다.

네트워크가 연결된 컴퓨터들은 함께 바이러스에 걸리게 된다.

첫째 줄 : 컴퓨터의 수

둘째 줄 : 네트워크 상 직접 연결된 컴퓨터 쌍의 수

N 줄 : 네트워크 상 직접 연결된 컴퓨터 번호 쌍

이러한 입력이 있을 때, 1번 컴퓨터의 감염으로 인해 바이러스에 걸리게 되는 컴퓨터의 수를 구하자.

 

2606번 바이러스 풀이

[시도1] 맞았습니다!! with 솔루션

n = int(input())
l = int(input())

graph = [[] for _ in range(n+1)]
for _ in range(l):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

visited = [0] * (n+1)

def dfs(graph, v, visited):
  visited[v] = 1
  for i in graph[v]:
    if visited[i] == 0:
      dfs(graph, i, visited)

dfs(graph, 1, visited)
print(sum(visited)-1)

DFS를 이용해서 코드를 작성했다.

1. 우선 graph를 만든다. 단, 노드들이 1부터 시작하므로 0번은 비워두고 n+1번까지로 해서 빈 2차원 배열을 생성한다. 입력받은 값과 연결된 노드들을 append로 추가해준다. 예를 들어 1번 노드는 2, 5와 연결되어 있으므로 graph[1]은 [2, 5]가 된다. 

2. visited로 0으로 초기화된 배열을 생성한다. 이 또한 0번 인덱스를 비워두므로 n+1까지로 생성해준다.

3. dfs 알고리즘은 함수로 생성해서 현재 노드 v에 방문(바이러스 감염)을 했으면 1로 바꾸고 해당 노드의 연결된 노드들 graph[v] 중에서 하나씩(i) 살펴본다. 만약 0이면, 아직 방문하지 않은 곳이므로 dfs함수를 재귀적으로 호출하여 해당 노드를 다시 1로 바꾸고 인접 노드들을 살피게 되는 것이다. 당연히 0이 아니고 이미 방문한 곳이면 그럴 필요가 없겠죠?!

4. 최종적으로는 방문한 곳을 다 더한 후에 1번 노드의 방문은 제외하므로 -1을 해준 값을 출력한다.

 

사실 다른 해답들을 참고했으니.. 당연히 맞았지만 ㅠㅠ

해답을 보면 안 되는데 자꾸 포기하고 해결 방법이 떠오르지 않아서 해답을 찾아보게 된다... 분발하자!!

 

https://www.acmicpc.net/problem/2606

2606번: 바이러스