Backjoon 2606번 바이러스

백준 알고리즘

• 2606번 바이러스

---

파이썬을 사용하였습니다.
단계별로 풀어보기 DFS와 BFS에 두번째 단계에 있는 문제입니다.

---

• 입력

  1. 첫줄에 N개의 컴퓨터의 수가 주어집니다.
  2. 둘째줄에 연결되어있는 컴퓨터 쌍의 갯수가 주어집니다.
  3. 셋째줄 부터 연결되어있는 컴퓨터 쌍의 이름이 주어집니다.

• 출력
  1번 컴퓨터를 통해 바이러스에 감염되는 컴퓨터 수를 출력

---

입력 예시

DFS를 사용하면 간단하게 풀 수 있습니다.
stact이라 적혀있는 리스트에 가장먼저 시작하는 정점을 append 합니다.
이제 stact의 가장 마지막 부분을 뽑아냅니다. 뽑아낸 정점이 visit에 없으면 visit에 추가하고
뽑아낸 정점을key로 가지는 리스트 values를 정렬해서 extend합니다.
이 과정을 stact에 리스트가 빈 리스트가 되거나 visit에 모든 정점이 나타나면 종료합니다.
https://dongyeon94.github.io/DYblog/backjoon/2020/02/06/backjoon1260.html
DFS에 대한 자세한 설명은

• 1260번
  1260번 DFS와 BFS해설에 자세하게 나타나 있습니다.

---

정답 코드

gragh ={}
n  = int(input())
line = int(input())

for i in range(n):
    gragh[i+1]=[]

for i in range(line):
    s,t = map(int, input().split(' '))
    gragh[s].append(t)
    gragh[t].append(s)



def DFS(gra,start):
    visit =[]
    stact = []
    stact.append(start)
    while stact:
        node  = stact.pop()
        if node not in visit:
            visit.append(node)
            try:
                stact.extend(gra[node])
            except:
                pass
    visit = list(set(visit))
    return len(visit)

print(DFS(gragh,1)-1)