[백준 2606] 바이러스 (Python)

2606번: 바이러스

from sys import stdin
com_dic = {}
for i in range(int(stdin.readline())) :
    com_dic[i+1] = set()
for _ in range(int(stdin.readline())) :
    temp = list(map(int, stdin.readline().split()))
    com_dic[temp[0]].add(temp[1])
    com_dic[temp[1]].add(temp[0])
  
def dfs(start, com_dic) :
  for i in com_dic[start] :
    if i not in result :
        result.append(i)
        dfs(i, com_dic)
  return result

result = []
result = dfs(1, com_dic)
result.remove(1)
print(len(result))

 dfs 문제였다. 해결하기 어려워 다른 분의 코드를 참고해서 정답을 맞혔는데 dfs, bfs는 알고 있어도 응용이 너무 어려운 것 같다.

 연결 관계를 표시하기 위해, 각 번호마다 set을 만들어두었고, 문제가 주어준 것에 따라 서로 연결시켰다. 그래야 알고리즘에 따라 방문을 덜하고 넘어가더라도 남은 것도 추가 방문 가능하기 때문이다. 그렇게 not in result를 통하여 한 번 방문한 것들의 list에서 시작 지점인 1을 제외하고 출력하며 문제를 마무리.