[백준] 2606 문제 in 파이썬

백준 2606번 : 바이러스

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

문제

풀이

착각했던 부분

• 예전에 풀었던 BFS 코드를 그대로 활용해 보려고 했는데,
  그 코드는 BFS(그래프, 시작노드, 도착노드)를 입력 받아 경로를 출력하는 코드였다. 하지만, 이 문제에서는 굳이 도착노드를 입력 받을 필요가 없다.
  그냥 처음부터 끝까지 탐색하여 연결된 노드 수를 구하는 것이기 때문이다.
  그래서 그냥 그래프와 시작노드만 입력 받는 코드로 문제를 풀었다.
• 문제 자체는 그래프에 연결된 노드를 딕셔너리 형식으로 저장하고 단순 BFS로 풀면 되는 거라 어렵진 않았다.

아쉬 부분

• 사실 시작노드도 필요 없는 거였는데… 그냥 그래프만 입력하는 코드를 작성할 걸 그랬다. 🥹

기본 로직

• 딕셔너리로 인접노드 저장. 양방향 그래프로 저장하는 방식을 택함.
• BFS : 시작노드를 입력 받아 시작노드로부터 인접한 노드로 그래프를 탐색함. 이때, vstd 배열을 통하여 방문한 노드를 표시함.
• vstd 배열의 크기에서 -1한 값을 return. (시작노드도 함께 들어가있기 때문에)

완성된 코드