2023.01.14 백준 바이러스

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

2606번: 바이러스

 

import sys
from collections import defaultdict

input = sys.stdin.readline

def dfs(v = 1,visited = []):
    if v in visited: # 1번째 탈출조건 : 만약 방문한적이 있다면 탈출
        return
    visited.append(v) # 방문한 곳 추가
    for i in graph_dict[v]: # 있는 곳에서 방문 할 수 있는곳 돌기 2번째 탈출 조건: 방문 할 수 있는 곳이 없으면 탈출
        dfs(i,visited) # 방문 가능한 곳 재귀로 돌기
    return len(visited) - 1 # 바이러스 걸린 컴퓨터의 개수 반환(1번 컴퓨터 제외)

n = int(input().strip()) #  컴퓨터의 개수

m = int(input().strip()) # 간선의 개수

graph = [list(map(int,input().split())) for _ in range(m)] # 리스트로 받기
graph_dict = defaultdict(list) # 받은걸 dict 형태로 저장 (양방향이기 때문에 2번씩 추기해줌)
for i in graph:
    graph_dict[i[0]].append(i[1])
    graph_dict[i[1]].append(i[0])

#print(graph_dict)
#defaultdict(<class 'list'>, {1: [2, 5], 2: [1, 3, 5], 3: [2], 5: [1, 2, 6], 6: [5], 4: [7], 7: [4]})

print(dfs())

dfs를 사용해서 갈 수 있는 곳을 돌면서 간 곳의 개수를 구해주는 프로그램을 만들었다.

간선의 방향이 양방향이기 때문에 graph_dict에 양방향으로 dict에 추가 했다.

collections의 defaultdict를 사용해서 dict의 key 가 초기화가 안되어 있을 때 list로 초기화 하게 만들었다.