코드

# 컴퓨터의 수 (1 ~ 100) (노드의 개수)
v = int(input())

# 연결되어 있는 컴퓨터 쌍의 수 (간선의 개수)
e = int(input())

# 연결 상태를 입력받을 리스트
# 인덱스 번호와 노드 번호를 통일시키기 위해서 N + 1 크기로 만듬
link = [[] for _ in range(v+1)]

# 컴퓨터 간의 연결 상태
for _ in range(e):
    a, b = map(int, input().split())
    link[a].append(b)
    link[b].append(a)
    
def dfs(link, v, visited):
    visited[v] = True
    
    for i in link[v]:
        if not visited[i]:
            dfs(link, i, visited)        

# 1번 컴퓨터가 방문하였는지 체크할 리스트
visited = [False] * len(link)

# 1번 컴퓨터가 웜 바이러스 시초
dfs(link, 1, visited)

# 1번 컴퓨터를 통해 바이러스가 걸리게 되는 컴퓨터의 수를 구해라
# => 1번 컴퓨터는 제외해야하므로 -1
print(len([x for x in visited if x == True]) - 1)

문제 해설

탐색 알고리즘 참고

탐색 알고리즘 관련 문제이다. DFS를 이용하여 해결하였는데, 아직 기본기가 많이 부족한게 확연하게 느껴진다.ㅠㅠ

댓글남기기

참고