백준 바이러스 코드 및 해설 (파이썬)

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

2606번: 바이러스

 

입력을 받아와 인접 리스트로 바꿔주고, 이를 다시 list of list로 변환하는데, 이때 i번째 리스트에는 i번째 컴퓨터와 직접 연결되어 있는 컴퓨터들의 번호가 저장됩니다.
이를 이용해 시작점을 1로 하고 dfs 함수를 수행해줍니다. visited 리스트 중 1번 컴퓨터를 제외한 컴퓨터들의 개수를 sum을 이용해 구한 후 반환합니다.

 

https://codlingual.tistory.com/182

DFS, BFS

 

import sys

# 입력 받아오기 
inputs = list(map(int, sys.stdin.read().split()))
# 총 컴퓨터 개수 
N = inputs[0]

# 인접 리스트 
adjs = []
for i in range(0,len(inputs[2:]),2):
    adjs.append(inputs[2:][i:i+2])

# 인접 행렬
graph = [[] for _ in range(N+1)]

for adj in adjs:
    a, b = adj
    graph[a].append(b)
    graph[b].append(a)

    
def dfs(start, graph, visited):
    visited[start] = True
    
    for adj in graph[start]:
        if not visited[adj]: 
            dfs(adj, graph, visited)
            
    return visited


visited = [False] * (N+1)
visited = dfs(1, graph, visited)

# 1은 제외하고 방문한 컴퓨터의 개수 세기 
print(sum(visited)-1)